LeetCode刷题笔记(十二): 链表

算法介绍：链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。

代码实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

补充：由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：一是尽量处理当前节点的下一个节点而非当前节点本身，二是建立一个虚拟节点(dummy node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个dummy存在，返回dummy->next即可。

一、链表的基本操作

题目一：反转链表
翻转一个链表。
示例图

解答：

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* res = nullptr;
        while (head != nullptr) {
            ListNode* next = head->next;
            head->next = res;
            res = head;
            head = next;
        }
        return res;
    }
};

提示：就是简单的模拟，注意操作的先后顺序。

题目二：合并两个有序链表
给定两个增序的链表，试将其合并成一个增序的链表。
示例图

解答：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* res = new ListNode();
        ListNode* opList = res;
        while (list1 != nullptr || list2 != nullptr) {
            ListNode* temp = nullptr;
            if (list1 == nullptr || list2 != nullptr && list1->val >= list2->val) {
                temp = new ListNode(list2->val);
                list2 = list2->next;
            } else if (list2 == nullptr || list1 != nullptr && list1->val < list2->val) {
                temp = new ListNode(list1->val);
                list1 = list1->next;
            }
            opList->next = temp;
            opList = opList->next;
        }
        return res->next;
    }
};

提示：注意边界的nullptr情况。

题目三：两两交换链表中的节点
给定一个链表，交换每个相邻的一对节点。
示例图

解答：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* prev = nullptr;
        ListNode* res = head->next;
        while(head != nullptr && head->next != nullptr) {
            ListNode* next = head->next;
            head->next = next->next;
            next->next = head;
            if (prev != nullptr) prev->next = next;
            prev = head;
            head = head->next;
        }
        return res;
    }
};

提示：不是很难，但需要注意的是要记录prev用于把next加入链表。

二、其他链表技巧

题目一：相交链表
给定两个链表，判断它们是否相交于一点，并求这个相交节点。
示例图

解答：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *list1 = headA, *list2 = headB;
        while (list1 != list2) {
            list1 = list1 != nullptr ? list1->next : headB;
            list2 = list2 != nullptr ? list2->next : headA;
        }
        return list1;
    }
};

提示：假设链表A的头节点到相交点的距离是a，链表B的头节点到相交点的距离是b，相交点到链表终点的距离为c。我们使用两个指针，分别指向两个链表的头节点，并以相同的速度前进，若到达链表结尾，则移动到另一条链表的头节点继续前进。按照这种前进方法，两个指针会在a+b+c次前进后同时到达相交节点。

题目二：回文链表
以O(1)的空间复杂度，判断链表是否回文。
示例图

解答：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> stack;
        ListNode *fast = head, *slow = head;
        while (fast != nullptr) {
            stack.push_back(slow->val);
            slow = slow->next;
            fast = fast->next;
            if (fast != nullptr) fast = fast->next;
            else stack.pop_back();
        }
        while (slow != nullptr) {
            if (stack.back() == slow->val)
                stack.pop_back();
            slow = slow->next;
        }
        return stack.empty();
    }
};

提示：使用反转链表即可完成O(1)的空间复杂度，这里给出另一种写法。

题目三：删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
示例图

解答：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // if (head->next == nullptr) return nullptr;
        ListNode *list1 = head, *list2 = head;
        ListNode *prev = nullptr;
        while (n--)
            list2 = list2->next;
        while (list2 != nullptr) {
            prev = list1;
            list1 = list1->next;
            list2 = list2->next;
        }
        if (prev == nullptr) return list1->next;
        prev->next = list1->next;
        delete list1;
        return head;
    }
};

提示：本质上也是一种快慢指针，不知道为什么是中等题。

题目四：排序链表
给你链表的头结点head，请将其按升序排列并返回排序后的链表。
示例图

解答：

class Solution {
    int getListLength(ListNode *head) {
        int length = 0;
        while (head) {
            length++;
            head = head->next;
        }
        return length;
    }

    ListNode *splitList(ListNode *head, int size) {
        ListNode *cur = head;
        for (int i = 0; i < size - 1 && cur; i++)
            cur = cur->next;
        if (cur == nullptr || cur->next == nullptr)
            return nullptr; 
        ListNode *next_head = cur->next;
        cur->next = nullptr; 
        return next_head;
    }

    pair<ListNode *, ListNode *> mergeTwoLists(ListNode *list1, ListNode *list2) {
        ListNode dummy;         
        ListNode *cur = &dummy; 
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; 
                list1 = list1->next;
            } else {                      
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; 
        while (cur->next) cur = cur->next;
        return {dummy.next, cur};
    }

public:
    ListNode *sortList(ListNode *head) {
        int length = getListLength(head); 
        ListNode dummy(0, head);          
        for (int step = 1; step < length; step *= 2) {
            ListNode *new_list_tail = &dummy; 
            ListNode *cur = dummy.next;       
            while (cur) {
                ListNode *head1 = cur;
                ListNode *head2 = splitList(head1, step);
                cur = splitList(head2, step); 
                auto [head, tail] = mergeTwoLists(head1, head2);
                new_list_tail->next = head;
                new_list_tail = tail; 
            }
        }
        return dummy.next;
    }
};