题目：24. 两两交换链表中的节点
Leetcode原题：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
思考历程与知识点：
因为头结点没有前一个节点
所以为了让所有节点都能采用同一种调换方式，选择用虚拟头结点的写法。
虚拟头结点可以理解为头结点的一个替身。
原来是头结点为老大，后面一群小弟，前面没东西。
现在新立一个替身，
让替身指向头结点后，头结点再指向后面的小弟们。
这样，现在的老大就是那个替身，
而真正的头结点和其他小弟一样，都跟在后面，
这样就可以用同一种方法进行调换了。
题解： /** * Definition for singly-linked list. * 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* swapPairs(ListNode* head) { ListNode* dummyhead = new ListNode(0); dummyhead -> next = head; ListNode* cur = dummyhead; while(cur -> next != nullptr && cur -> next -> next != nullptr) { ListNode* tmp = cur -> next; ListNode* tmp2 = cur -> next -> next -> next ; cur -> next = cur ->next ->next; cur -> next ->next = tmp; cur -> next ->next ->next = tmp2; cur = cur ->next ->next; } return dummyhead -> next; } };
其他语言版本：
java： class Solution { public ListNode swapPairs(ListNode head) { ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点 dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作 ListNode cur = dumyhead; ListNode temp; // 临时节点，保存两个节点后面的节点 ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点 ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点 while (cur.next != null && cur.next.next != null) { temp = cur.next.next.next; firstnode = cur.next; secondnode = cur.next.next; cur.next = secondnode; // 步骤一 secondnode.next = firstnode; // 步骤二 firstnode.next = temp; // 步骤三 cur = firstnode; // cur移动，准备下一轮交换 } return dumyhead.next; } } python： # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: dummy_head = ListNode(next=head) current = dummy_head # 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了 while current.next and current.next.next: temp = current.next # 防止节点修改 temp1 = current.next.next.next current.next = current.next.next current.next.next = temp temp.next = temp1 current = current.next.next return dummy_head.next
题目： 19.删除链表的倒数第N个节点
Leetcode原题：19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
思考历程与知识点：
删除倒数第n个节点。
因为链表像一串小火车，你只知道火车头的位置。
要想知道全长，你只能从火车头一节一节车厢往后找。
当你到达需要删除的车厢时，你并不知道你已经到了，因为只有知道全长才能知道倒数第n个是哪一个，
找完全部后才知道一共有多少个车厢。
所以要想删掉倒数第n个，并且只需要遍历一次的情况下，
需要想办法知道什么时候已经到达需要删除的车厢了。
双指针：设置两个指针，中间隔着n个距离，当第二个指针到达最后一个节点时，第一个指针就是倒数第n个的距离，很简单的。
题解：
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != NULL) { fast = fast->next; } fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点 while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; // ListNode *tmp = slow->next; C++释放内存的逻辑 // slow->next = tmp->next; // delete nth; return dummyHead->next; } };
其他语言版本：
java: public ListNode removeNthFromEnd(ListNode head, int n){ ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode fastIndex = dummyNode; ListNode slowIndex = dummyNode; //只要快慢指针相差 n 个结点即可 for (int i = 0; i < n ; i++){ fastIndex = fastIndex.next; } while (fastIndex.next != null){ fastIndex = fastIndex.next; slowIndex = slowIndex.next; } //此时 slowIndex 的位置就是待删除元素的前一个位置。 //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解 slowIndex.next = slowIndex.next.next; return dummyNode.next; } python: # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: # 创建一个虚拟节点，并将其下一个指针设置为链表的头部 dummy_head = ListNode(0, head) # 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点 slow = fast = dummy_head # 快指针比慢指针快 n+1 步 for i in range(n+1): fast = fast.next # 移动两个指针，直到快速指针到达链表的末尾 while fast: slow = slow.next fast = fast.next # 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点 slow.next = slow.next.next return dummy_head.next
题目： 面试题 02.07. 链表相交
Leetcode原题：面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：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 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
思考历程与知识点：
如果一个节点一个节点找，那就是上面的线路挨个节点选一遍，
假设它是交点，然后每个都要在下面从头到尾找一圈，那复杂度就是O（N*N）,实在是太大了。
所以换个思路，
既然最后会汇合成一条线路，那就说明，两个链表最后几个肯定一样呀。
所以只要从后往前找，一直到两边不同的时候，就是分叉点了。
题解：
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA = headA; ListNode* curB = headB; int lenA = 0, lenB = 0; while (curA != NULL) { // 求链表A的长度 lenA++; curA = curA->next; } while (curB != NULL) { // 求链表B的长度 lenB++; curB = curB->next; } curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { swap (lenA, lenB); swap (curA, curB); } // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap--) { curA = curA->next; } // 遍历curA 和 curB，遇到相同则直接返回 while (curA != NULL) { if (curA == curB) { return curA; } curA = curA->next; curB = curB->next; } return NULL; } };
其他语言版本：
java: public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; int lenA = 0, lenB = 0; while (curA != null) { // 求链表A的长度 lenA++; curA = curA.next; } while (curB != null) { // 求链表B的长度 lenB++; curB = curB.next; } curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { //1. swap (lenA, lenB); int tmpLen = lenA; lenA = lenB; lenB = tmpLen; //2. swap (curA, curB); ListNode tmpNode = curA; curA = curB; curB = tmpNode; } // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap-- > 0) { curA = curA.next; } // 遍历curA 和 curB，遇到相同则直接返回 while (curA != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; } } python: class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: lenA, lenB = 0, 0 cur = headA while cur: # 求链表A的长度 cur = cur.next lenA += 1 cur = headB while cur: # 求链表B的长度 cur = cur.next lenB += 1 curA, curB = headA, headB if lenA > lenB: # 让curB为最长链表的头，lenB为其长度 curA, curB = curB, curA lenA, lenB = lenB, lenA for _ in range(lenB - lenA): # 让curA和curB在同一起点上（末尾位置对齐） curB = curB.next while curA: # 遍历curA 和 curB，遇到相同则直接返回 if curA == curB: return curA else: curA = curA.next curB = curB.next return None
