双指针
基础知识
1.介绍
双指针是一种思想或一种技巧，并不是特别具体的算法。
具体就是用两个变量动态存储两个结点，方便我们进行一些操作。通常用在线性的数据结构中。
特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。
2.分类
常见的双指针方式：
- 同速指针：链表上两个指针，一个先出发，另一个后出发并以相同的速度跟随。
- 求链表的逆：通过临时指针让双指针同步前行
- 求链表倒数第k个元素：先让第一个指针前进k步，然后两个指针同样的速度前进，第一个指针走到尽头，则后面的指针为倒数第k个元素
- 快慢指针：链表上两个指针从同一节点出发，其中一个指针前进速度比另一个指针快（比如，是另一个指针的两倍）
- 计算链表的中点：快慢指针从头节点出发，快指针向前移动两个节点，满指针向前移动一个节点，最终当快指针到达终点的时候，满指针指向中间的节点。
- 判断链表是否有环：快慢指针从头节点出发，如果链表中存在环，两个指针最终会在环中相遇
- 求链表中环的长度：只要相遇后一个指针不动，另一个指针前进直到相遇计算长度即可。
题目解析
反转链表
1.题目描述
2.解析思路及代码
- 迭代：使用两个指针cur和prev，初始情况cur指向head，prev指向null，然后保证cur.next = prev，两个指针同时向右移动继续该操作直到cur只想空，这个时候prev指向的节点就是head
- 递归：将大问题分成小问题，将整个链表逆转，先假设链表后部分已经逆转，因此只需要修改当前节点的next的下一个指向当前节点即可，当前节点的next指向null，返回新节点，详细思路如下。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
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 = next
class 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 = next
class 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 = next
class 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