目录
一、反转链表
1.分析
给定单链表头结点，反转链表之后返回新的头结点。
思路一：翻转指针
原本1号指针指向下一个节点2的，但是将1号指针翻转之后指向空，一直翻转直到5指向空翻转为5指向4.
所以我们就需要3个变量，一个节点存放指向其他节点的信息，另一个节点是被指向的节点，还需要一个节点来存放下一个节点的信息
思路2：头插法
将已知链表存放在一个新的链表中，将已知链表的每一个节点头插进新的链表中，需要三个变量：一个变量存放新的链表的节点信息，一个变量存放下一个节点的信息，一个变量来存放当前位置的信息
2.翻转指针
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL)
{
return NULL;
}
struct ListNode* n1 = NULL;//被指向的节点
struct ListNode* n2 = head;//已知节点
struct ListNode* n3 = n2->next;//存下一个节点的位置
while (n2 != NULL)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
{
n3 = n3->next;
}
}
return n1;
}
3.头插法
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
二、链表的中间结点
1.分析
给定链表头结点，找出链表中间节点。
思路1：求长度，找中间值
定义一个变量len来表示长度，先遍历一遍链表，求出链表长度，然后直接就可以得出中间节点的位置
思路2：快慢指针
定义两个指针，一个slow一个fast，fast走两步，slow走一步，当fast到达最后一个节点或者fast出了链表之后，slow指针刚好到达中间节点，图示:
1.求长度，找中点
struct ListNode* middleNode(struct ListNode* head) {
int len = 0;
struct ListNode* p1 = head;
while (p1)
{
len++;
p1 = p1->next;
}
for (int i = 0;i < len / 2;i++)
{
head = head->next;
}
return head;
}
2.快慢指针
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
三、合并两个有序链表
1.分析
思路1：尾插法
由上图可知可以创建一个新的链表，然后依次把两个链表中小的数尾插进新的链表，准备两个节点，一个节点遍历新的链表，一个节点始终指向新链表的头结点，用两个链表依次比较来填充新的链表
思路2：带哨兵位的头结点
利用带哨兵位的头结点，就排除了第一个指针为空的情况，就可以直接判断两个链表的val的大小。
2.尾插法
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* head = NULL, * tail = NULL;
while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
if (tail == NULL)
{
head = tail = list1;
}
else
{
tail->next = list1;
tail = tail->next;
}
list1 = list1->next;
}
else
{
if (tail == NULL)
{
head = tail = list2;
}
else
{
tail->next = list2;
tail = tail->next;
}
list2 = list2->next;
}
}
if (list1 != NULL)
{
tail->next = list1;
}
if (list2 != NULL)
{
tail->next = list2;
}
return head;
}
注：可以提前准备头结点，省去两个判断是否为空的if语句
算法优化：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* head = NULL, * tail = NULL;
if (list1->val < list2->val)
{
head = tail = list1;
list1 = list1->next;
}
else
{
head = tail = list2;
list2 = list2->next;
}
while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = tail->next;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
}
if (list1 != NULL)
{
tail->next = list1;
}
if (list2 != NULL)
{
tail->next = list2;
}
return head;
}
3.带哨兵位的头节点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* head = NULL, * tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = tail->next;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
}
if (list1 != NULL)
{
tail->next = list1;
}
if (list2 != NULL)
{
tail->next = list2;
}
return head->next;
}
四、环形链表
1.分析
思路：通过快慢指针，创建两个指针，一个fast指针，一个slow指针，slow指针一次走一步，fast指针一次走两步，因为fast指针走的快，所有有两种情况。
第一种情况：
第二种情况：
第二种情况就是环形链表，因为fast走的快所以fast先进入环形区域，所以fast在环形区域中已知旋转，当slow进入环形区域中时solw和fast最终会相遇，所以结束标志就是fast==slow如果是非环形链表的话直接就出循环了。
2.快慢指针
bool hasCycle(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (slow == fast)
{
return true;
}
}
return false;
}
