1.介绍
双指针是一种思想或一种技巧，并不是特别具体的算法。
具体就是用两个变量动态存储两个结点，方便我们进行一些操作。通常用在线性的数据结构中。
特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。
2.分类
常见的双指针方式：
同速指针：链表上两个指针，一个先出发，另一个后出发并以相同的速度跟随。
求链表的逆：通过临时指针让双指针同步前行求链表倒数第k个元素：先让第一个指针前进k步，然后两个指针同样的速度前进，第一个指针走到尽头，则后面的指针为倒数第k个元素 快慢指针：链表上两个指针从同一节点出发，其中一个指针前进速度比另一个指针快（比如，是另一个指针的两倍）
计算链表的中点：快慢指针从头节点出发，快指针向前移动两个节点，满指针向前移动一个节点，最终当快指针到达终点的时候，满指针指向中间的节点。判断链表是否有环：快慢指针从头节点出发，如果链表中存在环，两个指针最终会在环中相遇求链表中环的长度：只要相遇后一个指针不动，另一个指针前进直到相遇计算长度即可。 题目解析 反转链表
1.题目描述
题目链接
2.解析思路及代码
迭代：使用两个指针cur和prev，初始情况cur指向head，prev指向null，然后保证cur.next = prev，两个指针同时向右移动继续该操作直到cur只想空，这个时候prev指向的节点就是head递归：将大问题分成小问题，将整个链表逆转，先假设链表后部分已经逆转，因此只需要修改当前节点的next的下一个指向当前节点即可，当前节点的next指向null，返回新节点，详细思路如下。
class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } // recursive public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }}
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def reverseList(self, head: ListNode) -> ListNode: cur = head prev = None while cur: next = cur.next cur.next = prev prev = cur cur = next return prev # recursive def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head newHead = self.reverseList(head.next) head.next.next = head head.next = None return newHead
删除链表的倒数第 N 个结点1.题目描述
题目链接
2.解题思路及代码
双指针：让两个指针分别指向head和空节点（空节点的下一个节点是head），然后让指向head的走n步，然后指向head和空节点的两个指针同时往下走直到指向head的为空，这个时候第二个指针就是指向倒数第n个节点的前一个节点，然后删除下一个节点即可。
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode head1 = new ListNode(); head1.next = head; ListNode fast = head; ListNode slow = head1; while (n > 0) { fast = fast.next; n -- ; } while (fast != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head1.next; }
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: head1 = ListNode(0, head) slow = head1 fast = head while n > 0: fast = fast.next n -= 1 while fast: fast = fast.next slow = slow.next slow.next = slow.next.next return head1.next
排序链表1.题目描述
题目链接
2.解题思路及代码
使用哈希表映射每个数字的出现次数，然后找出只出现一次的元素获取答案的每一位上的数字，因为其他数都出现三次，因此答案的每一位数字等于所有数字出现的结果和模3，注意如果目标语言不区分有符号数和无符号数，最高位需要特判。
public ListNode sortList(ListNode head) { return sortList(head, null); } public ListNode sortList(ListNode head, ListNode tail) { if (head == null) { return head; } if (head.next == tail) { head.next = null; return head; } ListNode slow = head, fast = head; while (fast != tail) { slow = slow.next; fast = fast.next; if (fast != tail) fast = fast.next; } ListNode mid = slow; ListNode list1 = sortList(head, mid); ListNode list2 = sortList(mid, tail); return merge(list1, list2); } public ListNode merge(ListNode head1, ListNode head2) { ListNode dummyHead = new ListNode(0); ListNode cur = dummyHead, cur1 = head1, cur2 = head2; while (cur1 != null && cur2 != null) { if (cur1.val > cur2.val) { cur.next = cur2; cur2 = cur2.next; } else { cur.next = cur1; cur1 = cur1.next; } cur = cur.next; } cur.next = (cur1 == null ? cur2 : cur1); return dummyHead.next; }
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: def sortFunc(head: ListNode, tail: ListNode) -> ListNode: if not head: return head if head.next == tail: head.next = None return head slow = fast = head while fast != tail: slow = slow.next fast = fast.next if fast != tail: fast = fast.next mid = slow return merge(sortFunc(head, mid), sortFunc(mid, tail)) def merge(head1: ListNode, head2: ListNode) -> ListNode: dummy = ListNode(0) cur, cur1, cur2 = dummy, head1, head2 while cur1 and cur2: if cur1.val <= cur2.val: cur.next = cur1 cur1 = cur1.next else: cur.next = cur2 cur2 = cur2.next cur = cur.next cur.next = cur2 if not cur1 else cur1 return dummy.next return sortFunc(head, None)
删除排序链表中的重复元素1.题目描述
题目链接
2.解题思路及代码
如果当前节点的下一个节点值等于当前节点，跳过下一个节点。
public ListNode deleteDuplicates(ListNode head) { if (head == null) return head; ListNode cur = head; while (cur.next != null) { if (cur.next.val == cur.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; }
class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: if not head: return head cur = head while cur.next: if cur.val == cur.next.val: cur.next = cur.next.next else: cur = cur.next return head
环形链表1.题目描述
题目链接
2.解题思路及代码
哈希表：有环一定会相遇，将节点保存到哈希表中，无环则一定可以遍历完快慢指针：快指针指向head的下一节点，慢指针指向head，然后快指针一次走两步，慢指针一次走一步，如果有环一定会相遇，否则fast指针一定会指向空，此时返回false
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) return false; fast = fast.next.next; slow = slow.next; } return true; }
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return False slow = head fast = head.next while fast != slow: if not fast or not fast.next: return False fast = fast.next.next slow = slow.next return True