链表 双指针

1. 快慢指针起点不一致起点不一致的快慢指针快指针先走 n 步然后两个指针同时移动快指针到达末尾时慢指针正好在目标位置。初始化两个指针 slow、fast 都指向头节点。快指针先行快指针先移动 n 步。同步移动两个指针同时移动直到快指针到达末尾fast Null。结果慢指针正好指向倒数第 n 个节点模板def findNthFromEnd(head, n): slow fast head # 快指针先走 n 步 for _ in range(n): fast fast.next # 两个指针同时移动 while fast: slow slow.next fast fast.next return slow # 慢指针指向倒数第 n 个节点例题19. 删除链表的倒数第 N 个结点 - 力扣LeetCode注意链表删除节点 → 一律用 dummy 虚拟头节点这样永远不会空指针永远能删头节点给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。示例 1输入head [1,2,3,4,5], n 2输出[1,2,3,5]/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */ public class Solution { public ListNode RemoveNthFromEnd(ListNode head, int n) { ListNode dummyHead new ListNode(); dummyHead.next head; ListNode fast dummyHead; ListNode slow dummyHead; for(int i0;in;i) { fast fast.next; } while(fast.next!null) { fastfast.next; slow slow.next; } slow.next slow.next.next; return dummyHead.next; } }2. 快慢指针步长不一致步长不一致的快慢指针两个指针从同一起点出发慢指针每次走 1 步快指针每次走 2 步。初始化两个指针都指向头节点。不同步长慢指针每次移动 1 步快指针每次移动 2 步。终止条件快指针到达末尾或无法继续移动。应用场景找中点、检测环、找交点等。模板def fastSlowPointer(head): slow fast head # 快指针每次走 2 步慢指针每次走 1 步 while fast and fast.next: slow slow.next # 慢指针移动 1 步 fast fast.next.next # 快指针移动 2 步 return slow # 慢指针指向中点或环的入口例题876. 链表的中间结点 - 力扣LeetCode给你单链表的头结点head请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。示例 1输入head [1,2,3,4,5]输出[3,4,5]解释链表只有一个中间结点值为 3 。示例 2输入head [1,2,3,4,5,6]输出[4,5,6]解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */ public class Solution { public ListNode MiddleNode(ListNode head) { ListNode fast head; ListNode slow head; while(fast!nullfast.next!null) { fast fast.next.next; slowslow.next; } return slow; } }3. 分离双指针分离双指针两个指针分别在不同的链表中移动常用于合并、比较等操作。初始化两个指针分别指向两个链表的头节点。条件移动根据具体问题决定何时移动哪个指针。终止条件其中一个链表遍历完毕或满足特定条件。应用场景有序链表合并、链表比较等。模板def separateTwoPointers(list1, list2): p1, p2 list1, list2 while p1 and p2: if condition1: # 两个指针同时移动 p1 p1.next p2 p2.next elif condition2: # 只移动第一个指针 p1 p1.next else: # 只移动第二个指针 p2 p2.next return result例题21. 合并两个有序链表 - 力扣LeetCode将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */ public class Solution { public ListNode MergeTwoLists(ListNode list1, ListNode list2) { ListNode dummyHead new ListNode(); ListNode current dummyHead; while(list1!nulllist2!null) { if(list1.vallist2.val) { current.next list1; list1 list1.next; } else { current.next list2; list2 list2.next; } current current.next; } if(list2!null) { current.next list2; } else { current.next list1; } return dummyHead.next; } }