链表高频题

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None```

基础题

206. 反转链表

Example:

```Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL```

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution - 递归

```class Solution:

res = self.reverseList(next_node)

return res```

Solution - 迭代**

```class Solution:
pre = None

while curr:
pre, curr.next, curr = curr, pre, curr.next

return pre```

Reference 超级好

重难点 (M->H)

138. 复制带随机指针的链表

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Solution

```class Node:
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random

class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':

di = {}

while node:
di[node] = Node(node.val, None, None)
node = node.next

while node:
di[node].next = di.get(node.next)
di[node].random = di.get(node.random)
node= node.next

21. 合并两个有序链表

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

```Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4```

Solution-递归

```class Solution(object):
def mergeTwoLists(self, l1, l2):
if not l1 or not l2: return l1 or l2

if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2```

Solution-迭代

```class Solution(object):
def mergeTwoLists(self, l1, l2):
if not l1 or not l2: return l1 or l2

dummy_node = ListNode(0)
curr = dummy_node

while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next

curr = curr.next

if l1 or l2: curr.next = l1 or l2

return dummy_node.next```

23. 合并K个排序链表

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

```Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6```

Solution

```class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
cnt = len(lists)
interval = 1
while interval < cnt:
for i in range(0, cnt-interval, interval*2):
lists[i] = self.merge2Lists(lists[i], lists[i+interval])
interval *= 2

return lists[0] if cnt else None

def merge2Lists(self, l1, l2):
if not l1 or not l2:
return l1 or l2

if l1.val <= l2.val:
l1.next = self.merge2Lists(l1.next, l2)
return l1

else:
l2.next = self.merge2Lists(l1, l2.next)
return l2```

25. K 个一组翻转链表

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Solution

powcai

```class Solution(object):

cnt = 0
while cur and cnt < k:
cur = cur.next
cnt += 1

if cnt == k:
cur = self.reverseKGroup(cur, k)
while cnt:
cnt -= 1

双指针技巧

141. 环形链表

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer `pos` which represents the position (0-indexed) in the linked list where tail connects to. If `pos` is `-1`, then there is no cycle in the linked list.

Example 1:

```Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.```

Solution

```class Solution:
def hasCycle(self, head: ListNode) -> bool:

while fast and fast.next:
slow, fast = slow.next, fast.next.next

if slow == fast: return True

return False```

142. 环形链表 II

Given a linked list, return the node where the cycle begins. If there is no cycle, return`null`.

Example 1:

```Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1```

Solution

```class Solution:

while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast: break

else:
return None

160. 相交链表

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Solution

```class Solution(object):

from collections import defaultdict
di = defaultdict(ListNode)

return None```

Dict做法，还可以用双指针

19. 删除倒数第N个节点

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

```Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.```

Solution

```class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

for _ in range(n):
fast = fast.next

while fast.next:
slow, fast = slow.next, fast.next

slow.next = slow.next.next

其他

234. 回文链表

Given a singly linked list, determine if it is a palindrome.

Example 1:

```Input: 1->2
Output: false```

Example 2:

```Input: 1->2->2->1
Output: true```

Follow up: Could you do it in O(n) time and O(1) space?

Solution

```class Solution(object):
left = []
while fast and fast.next:
left.append(slow.val)
slow, fast = slow.next, fast.next.next

if fast: left.append(slow.val)
right = slow.next

i = len(left)-1
while i>=0:
if right.val != left[i]: return False

right = right.next
i -= 1

return True```

328. 奇偶链表

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

```Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL```

Example 2:

```Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL```

Solution

```class Solution(object):

while odd and even and even.next:
odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next

2. 两数相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

```Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.```

Solution

```class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2: return l1 or l2

h = res = ListNode(0)
carry = 0

while l1 or l2:
cur_sum = 0
if l1:
cur_sum += l1.val
l1 = l1.next
if l2:
cur_sum += l2.val
l2 = l2.next

cur_sum += carry

carry = 1 if cur_sum>=10 else 0
h.next = ListNode(cur_sum%10)
h = h.next

if carry>0: h.next = ListNode(1)

return res.next```

148. 排序链表

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

```Input: 4->2->1->3
Output: 1->2->3->4```

Example 2:

```Input: -1->5->3->4->0
Output: -1->0->3->4->5```

Solution

```class Solution:
def sortList(self, head: ListNode) -> ListNode:
while fast and fast.next:
slow, fast = slow.next, fast.next.next
mid, slow.next = slow.next, None

# merge
h = res = ListNode(0)
while left and right:
if left.val<=right.val: h.next, left = left, left.next
else: h.next, right = right, right.next
h = h.next

h.next = left if left else right

return res.next```

mergesort

0 条评论

• Board相关题

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

• 数据结构基础之掌握5个常见的链表操作

最近在重新梳理学算法的知识，本文为链表常见操作复习的总结文章，会讲解常见的链表题目实现思路及附上答案，这些题目在leetcode上对应的题号也有给出，好好学习算...

• Python 之父的解析器系列之六：给 PEG 语法添加动作

花下猫语：Guido 的解析器系列更新了 7 篇，他的生产力真旺盛啊。这对于新的解析器来说是件好事，但对于我来说却是个不小的挑战：需要一定的时间和精力，而我对解...

• LeetCode 142：环形链表 II Linked List Cycle II

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

• LeetCode 142：环形链表 II Linked List Cycle II

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

• python中利用try..except来代替if..else

在有些情况下，利用try…except来捕捉异常可以起到代替if…else的作用。 比如在判断一个链表是否存在环的leetcode题目中，初始代码是这样的

• 每日一题-反转链表

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL