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
解析:
先使用快慢指针找到链表中点,再把链表切成两半
然后把后半段翻转,请参考206题反转链表
最后使用两个指针逐个比较两半元素是否相等
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 章 指针三剑客之链表
更多推荐
链表,遍历,笔记,LeetCode
发布评论