背景

前段时间，在知识星球立了一个Flag，这是总结Leetcode刷题的第三篇图文。

理论部分

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; }
• -> 获取的最后一个节点

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：反转链表

• 题号：206
• 难度：简单
• https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

输入: 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% 的用户

/*** 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% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if head is None or head.next is None:return headp1 = headp2 = Nonewhile p1 is not None:temp = p1.nextp1.next = p2p2 = p1p1 = tempreturn p2

题目2：删除链表的倒数第N个节点

• 题号：19
• 难度：中等
• https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的n保证是有效的。

进阶：

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

思路：利用双指针的方式

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

C# 语言

• 执行结果：通过
• 执行用时：104 ms, 在所有 C# 提交中击败了 86.93% 的用户
• 内存消耗：24.6 MB, 在所有 C# 提交中击败了 100.00% 的用户

/*** 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% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:p2 = headp1 = headwhile (n > 0):p1 = p1.nextn -= 1if (p1 is None):  # 移除头结点return head.nextwhile (p1.next):p2 = p2.nextp1 = p1.nextp2.next = p2.next.nextreturn head

题目3：删除排序链表中的重复元素

• 题号：83
• 难度：简单
• https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

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

示例 1:

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

示例 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% 的用户

/*** 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;elsep2 = p2.next;p1 = p1.next;}return head;}
}

Python 语言

• 执行结果：通过
• 执行用时：52 ms, 在所有 Python3 提交中击败了 33.88% 的用户
• 内存消耗：13.5 MB, 在所有 Python3 提交中击败了 12.75% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:if head is None:return headp1 = head.nextp2 = headwhile p1 is not None:if p1.val == p2.val:p2.next = p1.nextelse:p2 = p2.nextp1 = p1.nextreturn head

例题4：环形链表

• 题号：141
• 难度：简单
• https://leetcode-cn.com/problems/linked-list-cycle/

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

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

示例 1：

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

示例 2：

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

示例 3：

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

思路：利用双指针的方式

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

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

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

p1：1   3   5   2   4   1
p2：1   2   3   4   5   1

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

p1：1   3   1   3   1
p2：1   2   3   4   1

C# 语言

• 状态：通过
• 执行用时: 112 ms, 在所有 C# 提交中击败了 98.43% 的用户
• 内存消耗: 24.9 MB, 在所有 C# 提交中击败了 5.13% 的用户

/*** 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% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:p1 = headp2 = headwhile p1 is not None and p1.next is not None:p1 = p1.next.nextp2 = p2.nextif p1 == p2:return Truereturn False

题目5：排序链表

• 题号：148
• 难度：中等
• https://leetcode-cn.com/problems/sort-list/

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

示例 1:

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

示例 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% 的用户

/*** 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% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def sortList(self, head: ListNode) -> ListNode:if head is None:return headreturn self.mergeSort(head)def mergeSort(self, node: ListNode) -> ListNode:if node.next is None:return nodep1 = nodep2 = nodecute = Nonewhile p1 is not None and p1.next is not None:cute = p2p2 = p2.nextp1 = p1.next.nextcute.next = Nonel1 = self.mergeSort(node)l2 = self.mergeSort(p2)return self.mergeTwoLists(l1, l2)def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:pHead = ListNode(-1)temp = pHeadwhile l1 is not None and l2 is not None:if l1.val < l2.val:temp.next = l1l1 = l1.nextelse:temp.next = l2l2 = l2.nexttemp = temp.nextif l1 is not None:temp.next = l1if l2 is not None:temp.next = l2return pHead.next

总结

本篇图文首先说明了 Python 语言中的list不是链表而是一个动态数组，C# 语言中的List<T>也是动态数组。Python 中没有提供链表这种结构，C# 中提供了双向链表的结构LinkedList<T>。之后，我们通过五道Leetcode题目说明了双指针技术在链表问题中的应用，希望能够对大家有所帮助。目前 Flag 计划已经执行 60%，要努力，要努力！今天就到这里吧！See You！

当前活动

我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：