LeetCode-链表专题

1->2->3->NULL，链表是指向型结构
查找：随机访问的时间复杂度是O(n)
增删：删除和插入元素的时间复杂度都是O(1)

对于链表我们都用头结点来代表整个链表，给你一个链表的时候我们拿到的就是头节点。如果没有头结点证明整个链表为空，如果已经有头结点证明链表不为空。

虚拟头结点：由于链表中是用head节点来代替整个链表的，故头节点经常需要判断(head有还是没有来进行不同的操作)->可以通过设置一个哨兵的技巧简化代码，哨兵节点的值一直是NULL，不用考虑哨兵的问题，在哨兵眼里你是head还是不是head对其来说都是一样的。最后return的是 哨兵->next，因为我们已经不在乎head是不是之前的head了，保持next就行。

遍历：

head;
while (head)
{
    head = head->next;
}

对链表进行修改的时候，有些时候需要将头结点删掉，这样针对头结点有无需要进行判断头结点有无，针对有无的不同情况进行不同的操作(写很多if else)。定义一个哨兵节点(空节点)，这样在进行遍历的时候就不用考虑头节点。

dummy; dumm->next = head; p = dummy;
while (p) 
{

}

206 反转链表
注意：对于分析算法题里有一个重要的理念：上来要考虑到入口的边界条件

public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode* pre = NULL;
        ListNode* cur = head;

        while (cur)
        {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

92 反转链表II

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto tmp = dummy;

        for (int i = 0; i < left - 1; i ++)
            tmp = tmp->next;
        
        auto pre = tmp->next;
        auto cur = pre->next;
        for (int i = 0; i < right - left; i ++)
        {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        tmp->next->next = cur;
        tmp->next = pre;

        return dummy->next;
    }
};

21 合并两个有序链表
两路归并

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        auto p = list1, q = list2;
        auto dummy = new ListNode(-1);
        auto cur = dummy;

        while (p && q)
        {
            if (p->val <= q->val) 
            {
                cur->next = p;
                p = p->next;
                cur = cur->next;
            }
            else
            {
                cur->next = q;
                q = q->next;
                cur = cur->next;
            }
        }
        if (p) cur->next = p;
        if (q) cur->next = q;

        return dummy->next;
    }
};

快慢指针

19 删除链表的第N个节点
设计到删除头结点的要用到虚拟头结点
快指针先走n步，然后快指针和慢指针同时走，直到快指针走到终点，慢指针就走到了要删除点的前一个点，然后删除即可

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto slow = dummy, fast = dummy;

        while (n --)  fast = fast->next;

        while (fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;

        return  dummy->next;
    }
};

876 链表的中间节点
枚举一下奇偶的情况，奇数点的时候fast->next为空，偶数点的时候fast为空

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto slow = head, fast = head;

        while (fast && fast->next) // && 
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};

234 回文链表
不能直接通过索引找到链表的结尾，
找到链表的中点(分奇偶)，然后将中点的前半段进行翻转，再对比前后半段链表。
注意：while循环中的顺序必须先让fast走两步，再slow走一步。因为如果是slow走一步的同时要修改指针方向，fast再走两步就到不了原来想到的地方了。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        auto slow = head, fast = head;
        ListNode* pre = NULL;

        while (fast && fast->next)
        {
            fast = fast->next->next; // fast必须先走，因为后走之后，slow改变了原来的指针指向，fast就到不了该到的位置了    
            auto next = slow->next;
            slow->next = pre;
            pre = slow;
            slow = next;  
        }
        if (fast) slow = slow->next;

        while (pre && slow)
        {
            if (slow->val != pre->val) return false;
            pre = pre->next;
            slow = slow->next;
        }

        return true;
    }
};

160 相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;

        while (p != q)
        {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }

        return p;
    }
};

141 环型链表
有环和没有环的区别：两指针有没有相遇
两个指针有没有再次遇到，如果有环->相当于在环形操场跑->快指针跑的快就一定会慢指针套圈，两指针会相遇
如果没有环->相当于在直道跑->快指针跑的快，两指针一定不会遇到

class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto slow = head, fast = head;

        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) return true;
        }

        return false;
    }
};