LeetCode刷题笔记 链表 遍历链表

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 章 指针三剑客之链表

上一篇:环形链表(力扣简单题)(链表)


下一篇:剑指 Offer 23. 链表中环的入口结点