双指针是一种思想或一种技巧并不是特别具体的算法。具体就是用两个变量动态存储两个结点,来方便我们进行一些操作。通常用在线性的数据结构中。
特别是链表类的题目,经常需要用到两个或多个指针配合来记忆链表上的节点,完成某些操作。
•同速指针:链表上两个指针,一个先出发,另一个后出发并以相同的速度跟随。
•求链表的逆:通过临时指针让双指针同步前行•求链表倒数第k个元素:先让其中一个指针向前走k步,接着两个指针以同样的速度一起 向前进,直到前面的指针走到尽头了,则后面的指针即为倒数第k个元素
•快慢指针:链表上两个指针从同一节点出发,其中一个指针前进速度比另一个指针快(比 如,是另一个指针的两倍)
•计算链表的中点:快慢指针从头节点出发,每轮迭代中,快指针向前移动两个节点,慢
指针向前移动一个节点,最终当快指针到达终点的时候,慢指针刚好在中间的节点
•判断链表是否有环:快慢指针从头节点出发,如果链表中存在环,两个指针最终会在环 中相遇•求链表中环的长度:只要相遇后一个不动,另一个前进直到相遇算一下走了多少步就。
双指针常用于线性结构:链表,数组
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 :
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
输入:head = [1,2]
输出:[2,1]
输入:head = []
输出:[]
解题思路:
•方法1:遍历一遍使用列表存储元素,再进行反转,再遍历一遍将元素串起来
•方法2:通速指针方法,两个指针一前一后,使用中间变量保存下一个节点,之后再进行移动赋值
python实现
# 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:
if head is None or head.next is None:
return head
p1 = None
p2 = head
while p2: # 画图即可
tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
return p1 # p1在p2的前面,p2已经是末尾None
c++实现
/**
* 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* reverseList(ListNode* head) {
ListNode* p1 = nullptr;
ListNode* p2 = head;
while(p2 != nullptr)
{
ListNode* tmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmp;
}
return p1;
}
};
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
输入:head = [1], n = 1
输出:[]
输入:head = [1,2], n = 1
输出:[1]
解题思路:
•方法1:遍历一遍保存链表每个节点的val,转成列表之后,删除倒数第N个节点的值,再遍历一遍进行串联即可•方法2:快慢指针,一个先不动,一个先往前走n步,然后再两个一起走动,直到先走的指针到达末尾,则慢指针到达末尾第n-1个元素,再设置该处的元素x.next = x.next.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:
p1 = head
p2 = head
for i in range(n): # 快指针先走n步
p2 = p2.next
if not p2: # 如果已经走到末尾了,则表明应该删除头结点
return p1.next
while p2.next: # 这里是P2.next, 需要往前退一步
p1 = p1.next
p2 = p2.next
p1.next = p1.next.next
return head
c++实现
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* p1 = head;
ListNode* p2 = head;
while(n)
{
p2 = p2->next;
n--;
}
if(p2==nullptr)
{
return p1->next;
}
while(p2->next)
{
p1 = p1->next;
p2 = p2->next;
}
p1->next = p1->next->next;
return head;
}
};
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。否则,返回 false
。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
解题思路:
•方法1:遍历并存储节点到一个哈希表中,节点作为key,遍历时候如果发现该节点已经在哈希表中则表明有环•方法2:使用快慢指针,一个每次走一步,一个每次走两步,如果两者有重叠的话,则表明存在环路。
python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
p_slow = head
p_fast = head
while p_fast and p_fast.next: # 条件要增加一个判断p_fast是否是节点以及其下一个是否为节点
p_slow = p_slow.next
p_fast = p_fast.next.next
if p_slow == p_fast:
return True
return False
c++实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr)
{
return false;
}
ListNode* p_slow = head;
ListNode* p_fast = head;
while(p_fast && p_fast->next)
{
p_slow = p_slow->next;
p_fast = p_fast->next->next; // 走两步
if(p_slow == p_fast)
{
return true;
}
}
return false;
}
};
给定一个已排序的链表的头 head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:
输入:head = [1,1,2]
输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]
解题思路:
•方法1:使用栈的思想,如果后面入的元素与栈顶元素相同,就略过该元素,继续遍历•方法2:双指针,一前一后,后面的指针与前面的指针元素进行比较,如果是相同值,则后指针继续往后走。如果不相同,则前指针移动到后指针位置,后指针也往后移动一位。
python实现
跟前面比
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
pre_node = head
cur_node = head.next
while cur_node: # 要一直比较到末尾,这里用cur_node 不是cur_node.next
if pre_node.val == cur_node.val: # 与前面的节点进行相比
pre_node.next = cur_node.next
cur_node = cur_node.next
else:
pre_node = cur_node
cur_node = cur_node.next
return head
c++实现
跟后面比
/**
* 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* deleteDuplicates(ListNode* head) {
if(head==nullptr || head->next==nullptr)
{
return head;
}
ListNode* cur = head;
while(cur->next != nullptr)
{
if(cur->val == cur->next->val) // 与后面的元素进行相比较,如果后面的元素与cur元素相同,则略过该后面的元素
{
cur->next = cur->next->next;
}
else // 如果不相同,此时cur往后挪一个节点
{
cur = cur->next;
}
}
return head;
}
};
给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
示例 3:
输入:head = []
输出:[]
解题思路:
•方法1:遍历并使用列表保存,对列表进行排序,再遍历一遍将元素串起来•方法2:使用快慢指针将链表截断为两部分,使用递归的方法对子链表进行排序,再使用合并单链表的方式两两串联起来。递归排序的终止条件是链表的节点个数小于或等于,即当链表为空或者链表只包含1个节点时,不需要对链表进行拆分和排序
python实现
class Solution:
def sortList(self, head: ListNode) -> 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:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
return sortFunc(head, None)
c++实现
/**
* 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* sortList(ListNode* head) {
return sortFunc(head, nullptr);
}
ListNode* sortFunc(ListNode* head, ListNode* tail)
{
if(head==nullptr)
{
return head;
}
if(head->next == tail)
{
head->next = nullptr; // 断开
return head;
}
ListNode* slow = head;
ListNode* fast = head;
while(fast != tail)
{
slow = slow->next;
fast = fast->next;
if(fast != tail)
{
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortFunc(head, mid), sortFunc(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2)
{
ListNode* dummyHead = new ListNode(0);
ListNode* tmp = dummyHead;
ListNode* tmp1 = head1;
ListNode* tmp2 = head2;
while(tmp1!=nullptr && tmp2 != nullptr)
{
if(tmp1->val <= tmp2->val)
{
tmp->next = tmp1;
tmp1 = tmp1->next;
}
else
{
tmp->next = tmp2;
tmp2 = tmp2->next;
}
tmp = tmp->next;
}
if(tmp1 != nullptr)
{
tmp->next = tmp1;
}
else if(tmp2 != nullptr)
{
tmp->next = tmp2;
}
return dummyHead->next;
}
};