160 相交链表

给定两个链表，判断它们是否相交于一点，并求这个相交节点。

输入是两条链表，输出是一个节点。如无相交节点，则返回一个空节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解析：

​ 假设链表 A 的头节点到相交点的距离是 a，链表 B 的头节点到相交点的距离是 b，相交点到链表终点的距离为 c。

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

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

234 回文链表

以 O(1) 的空间复杂度，判断链表是否回文。

输入是一个链表，输出是一个布尔值，表示链表是否回文。

输入：head = [1,2,2,1]
输出：true

解析：

1. ​先使用快慢指针找到链表中点，再把链表切成两半

2. 然后把后半段翻转，请参考206题反转链表

3. 最后使用两个指针逐个比较两半元素是否相等

class Solution {
public:
    // 链表翻转
    ListNode* reverseList(ListNode* head) {
           ListNode *prev = nullptr, *next = head;
           while(head){
               next = head->next;
               head->next = prev;
               prev = head;
               head = next;
           }
           return prev;
       }

    bool isPalindrome(ListNode* head) {
        if(!head || !head->next){
            return true;
        }
        // 快慢指针找到链表中点
        ListNode *fast = head, *slow = head;
        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        
        // 不管链表长度为偶数还是奇数 slow 指向都是前半部分的最后一个节点
        fast = slow->next;
        fast = reverseList(fast);
        slow = head;
        // 比较两部分元素是否一致
        while(fast){
            if(slow->val != fast->val){
                return false;
            }
            slow = slow->next;
            fast = fast->next;
        }
        return true;
    }
};

19 删除链表的倒数第 N 个结点

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入是一个链表，输出删除倒数第 n 个节点的链表

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解析：

​ 和使用快慢指针找到链表中点的思路一样，让快指针先于慢指针 n 个节点出发，那么当快指针到达链表尾部时，慢指针刚好处于链表倒数第 n+1 个节点，删除其next节点即可。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow=head, *fast=head;
        // 快指针先走n步
        for(int i=0;i<n;++i){
            fast=fast->next;
        }
        if(!fast){
            head = head->next;
            return head;
        }
        while(fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        ListNode *delNode = slow->next;
        slow->next = delNode->next;
        delete delNode;
        return head;
    }
};

参考资料

LeetCode 101：和你一起轻松刷题(C++) 第 13 章 指针三剑客之链表