Leetcode刷题专题打卡——双指针

C# 和 Python 中的链表结构

本文主要来自Datawhale组队学习——双指针技术~

Python list 的源码地址:

https://github.com/python/cpython/blob/master/Include/listobject.h

https://github.com/python/cpython/blob/master/Objects/listobject.c

C# List<T> 的源码地址:

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

通过阅读源码,我们发现 Python 的 list 与 C# 的 List<T> 一致都是通过动态数组的方式来实现的。

Python 的内置结构中没有链表这种结构,而C# 的内置结构中封装了双向链表 LinkedList<T>,内部结点为 LinkedListNode<T>,源码地址如下:

https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs,df5a6c7b6b60da4f

LinkedListNode

  • public LinkedListNode<T> Next { get; } -> 获取下一个节点
  • public LinkedListNode<T> Previous { get; } -> 获取上一个节点
  • public T Value { get; set; } -> 获取或设置包含在节点中的值。

LinkedList

  • public LinkedListNode<T> AddFirst(T value); -> 添加包含指定的值的开头的新节点
  • public LinkedListNode<T> AddLast(T value); -> 添加包含指定的值的末尾的新节点
  • public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value); -> 添加包含在指定的现有节点前的指定的值的新节点
  • public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value); -> 添加包含指定的值中指定的现有节点后的新节点
  • public void AddFirst(LinkedListNode<T> node); -> 将指定的新节点添加的开头
  • public void AddLast(LinkedListNode<T> node); -> 将指定的新节点添加的末尾
  • public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode); -> 在指定的现有节点之前添加指定的新节点
  • public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode); -> 在指定的现有节点之后添加指定的新节点
  • public bool Remove(T value); -> 移除从指定的值的第一个匹配项
  • public void Remove(LinkedListNode<T> node); -> 移除指定的节点
  • public void RemoveFirst(); -> 删除的开始处的节点
  • public void RemoveLast(); -> 删除节点的末尾
  • public LinkedListNode<T> Find(T value); -> 查找包含指定的值的第一个节点。
  • public LinkedListNode<T> FindLast(T value); -> 查找包含指定的值的最后一个节点。
  • public void Clear(); -> 删除所有节点
  • public int Count { get; } -> 获取中实际包含的节点数
  • public LinkedListNode<T> First { get; } -> 获取的第一个节点
  • public LinkedListNode<T> Last { get; } -> 获取的最后一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void LinkedListSample()
{
LinkedList<int> lst = new LinkedList<int>();
lst.AddFirst(3);
lst.AddLast(1);
lst.AddLast(4);
foreach (int item in lst)
{
Console.Write(item+" ");
}
Console.WriteLine();

LinkedListNode<int> cur = lst.Find(3);
lst.AddBefore(cur, 2);
foreach (int item in lst)
{
Console.Write(item + " ");
}
Console.WriteLine();

lst.Remove(3);
foreach (int item in lst)
{
Console.Write(item + " ");
}
Console.WriteLine();
lst.Clear();
}

// 3 1 4
// 2 3 1 4
// 2 1 4

反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

思路:利用双指针的方式

p1作为前面的指针探路,p2作为后面的指针跟进,顺着链表跑一圈,搞定问题。

C# 语言

  • 状态:通过
  • 27 / 27 个通过测试用例
  • 执行用时: 116 ms, 在所有 C# 提交中击败了 97.50% 的用户
  • 内存消耗: 23.3 MB, 在所有 C# 提交中击败了 5.26% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/

public class Solution
{
public ListNode ReverseList(ListNode head)
{
if (head == null || head.next == null)
return head;

ListNode p1 = head;
ListNode p2 = null;
while (p1 != null)
{
ListNode temp = p1.next;
p1.next = p2;
p2 = p1;
p1 = temp;
}
return p2;
}
}

Python 语言

  • 执行结果:通过
  • 执行用时:36 ms, 在所有 Python3 提交中击败了 92.27% 的用户
  • 内存消耗:14.6 MB, 在所有 Python3 提交中击败了 17.65% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
p1 = head
p2 = None
while p1 is not None:
temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
return p2

删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第n个节点,并且返回链表的头结点。

示例

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明

给定的n保证是有效的。

进阶

你能尝试使用一趟扫描实现吗?

思路:利用双指针的方式

使用两个指针,前面的指针p1先走n步,接着让后面的指针p2p1同步走,p1走到终点,p2即走到要移除的结点位置。

C# 语言

  • 执行结果:通过
  • 执行用时:104 ms, 在所有 C# 提交中击败了 86.93% 的用户
  • 内存消耗:24.6 MB, 在所有 C# 提交中击败了 100.00% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution
{
public ListNode RemoveNthFromEnd(ListNode head, int n)
{
ListNode p1 = head;
ListNode p2 = head;

while (n > 0)
{
p1 = p1.next;
n--;
}

if (p1 == null) //移除头结点
{
return head.next;
}

while (p1.next != null)
{
p1 = p1.next;
p2 = p2.next;
}

p2.next = p2.next.next;
return head;
}
}

Python 语言

  • 执行结果:通过
  • 执行用时:48 ms, 在所有 Python3 提交中击败了 23.58% 的用户
  • 内存消耗:13.5 MB, 在所有 Python3 提交中击败了 7.83% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
p2 = head
p1 = head
while (n > 0):
p1 = p1.next
n -= 1

if (p1 is None): # 移除头结点
return head.next

while (p1.next):
p2 = p2.next
p1 = p1.next

p2.next = p2.next.next
return head

删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

1
2
输入: 1->1->2->3->3
输出: 1->2->3

思路:利用双指针的方式

p1作为前面的指针探路,p2作为后面的指针跟进,如果遇到重复元素,p2.next跳过去,p1跑完整个链表所有重复元素都被摘下来。

C# 语言

  • 执行结果:通过
  • 执行用时:160 ms, 在所有 C# 提交中击败了 5.23% 的用户
  • 内存消耗:25.9 MB, 在所有 C# 提交中击败了 5.72% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/

public class Solution
{
public ListNode DeleteDuplicates(ListNode head)
{
if (head == null)
return head;

ListNode p1 = head.next;
ListNode p2 = head;
while (p1 != null)
{
if (p1.val == p2.val)
p2.next = p1.next;
else
p2 = p2.next;
p1 = p1.next;
}
return head;
}
}

Python 语言

  • 执行结果:通过
  • 执行用时:52 ms, 在所有 Python3 提交中击败了 33.88% 的用户
  • 内存消耗:13.5 MB, 在所有 Python3 提交中击败了 12.75% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return head

p1 = head.next
p2 = head
while p1 is not None:
if p1.val == p2.val:
p2.next = p1.next
else:
p2 = p2.next
p1 = p1.next
return head

环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos是 -1,则在该链表中没有环。

示例 1

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

img

示例 2

1
2
3
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

img

示例 3

1
2
3
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

img

进阶

你能用 O(1)(即,常量)内存解决此问题吗?

思路:利用双指针的方式

通常情况下,判断是否包含了重复的元素,我们使用Hash的方式来做。对于单链表的这种场景,我们也可以使用双指针的方式。

第一个指针 p1 每次移动两个节点,第二个指针 p2 每次移动一个节点,如果该链表存在环的话,第一个指针一定会再次碰到第二个指针,反之,则不存在环。

比如:head = [1,2,3,4,5],奇数

1
2
p1:1   3   5   2   4   1
p2:1 2 3 4 5 1

比如:head = [1,2,3,4],偶数

1
2
p1:1   3   1   3   1
p2:1 2 3 4 1

C# 语言

  • 状态:通过
  • 执行用时: 112 ms, 在所有 C# 提交中击败了 98.43% 的用户
  • 内存消耗: 24.9 MB, 在所有 C# 提交中击败了 5.13% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public bool HasCycle(ListNode head) {
ListNode p1 = head;
ListNode p2 = head;

while (p1 != null && p1.next != null)
{
p1 = p1.next.next;
p2 = p2.next;
if (p1 == p2)
return true;
}
return false;
}
}

Python 语言

  • 执行结果:通过
  • 执行用时:56 ms, 在所有 Python3 提交中击败了 60.97% 的用户
  • 内存消耗:16.6 MB, 在所有 Python3 提交中击败了 11.81% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def hasCycle(self, head: ListNode) -> bool:
p1 = head
p2 = head
while p1 is not None and p1.next is not None:
p1 = p1.next.next
p2 = p2.next
if p1 == p2:
return True
return False

排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路:模仿并归排序的思路,典型的回溯算法。

如果待排的元素存储在数组中,我们可以用并归排序。而这些元素存储在链表中,我们无法直接利用并归排序,只能借鉴并归排序的思想对算法进行修改。

并归排序的思想是将待排序列进行分组,直到包含一个元素为止,然后回溯合并两个有序序列,最后得到排序序列。

对于链表我们可以递归地将当前链表分为两段,然后merge,分两段的方法是使用双指针法,p1指针每次走两步,p2指针每次走一步,直到p1走到末尾,这时p2所在位置就是中间位置,这样就分成了两段。

C# 语言

  • 状态:通过
  • 16 / 16 个通过测试用例
  • 执行用时: 124 ms, 在所有 C# 提交中击败了 100.00% 的用户
  • 内存消耗: 29 MB, 在所有 C# 提交中击败了 25.00% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/

public class Solution
{
public ListNode SortList(ListNode head)
{
if (head == null)
return null;
return MergeSort(head);
}

private ListNode MergeSort(ListNode node)
{
if (node.next == null)
{
return node;
}
ListNode p1 = node;
ListNode p2 = node;
ListNode cut = null;
while (p1 != null && p1.next != null)
{
cut = p2;
p2 = p2.next;
p1 = p1.next.next;
}
cut.next = null;
ListNode l1 = MergeSort(node);
ListNode l2 = MergeSort(p2);
return MergeTwoLists(l1, l2);
}

private ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
ListNode pHead = new ListNode(-1);
ListNode temp = pHead;

while (l1 != null && l2 != null)
{
if (l1.val < l2.val)
{
temp.next = l1;
l1 = l1.next;
}
else
{
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}

if (l1 != null)
temp.next = l1;

if (l2 != null)
temp.next = l2;

return pHead.next;
}
}

Python 语言

  • 执行结果:通过
  • 执行用时:216 ms, 在所有 Python3 提交中击败了 75.99% 的用户
  • 内存消耗:20.7 MB, 在所有 Python3 提交中击败了 28.57% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None:
return head
return self.mergeSort(head)

def mergeSort(self, node: ListNode) -> ListNode:
if node.next is None:
return node
p1 = node
p2 = node
cute = None
while p1 is not None and p1.next is not None:
cute = p2
p2 = p2.next
p1 = p1.next.next
cute.next = None
l1 = self.mergeSort(node)
l2 = self.mergeSort(p2)
return self.mergeTwoLists(l1, l2)

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
pHead = ListNode(-1)
temp = pHead
while l1 is not None and l2 is not None:
if l1.val < l2.val:
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next

if l1 is not None:
temp.next = l1
if l2 is not None:
temp.next = l2

return pHead.next
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

扫一扫,分享到微信

微信分享二维码
  • Copyrights © 2020 chenk
  • 由 帅气的CK本尊 强力驱动
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信