LeetCode刷题---链表

一、反转链表

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;
}