# 链表高频题

```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 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

16 篇文章16 人订阅

0 条评论

## 相关文章

22440

8300

8600

6600

### 面试官：Logback如何配置，才能提升TPS?

SpringBoot工程自带logback和slf4j的依赖，所以重点放在编写配置文件上，需要引入什么依赖，日志依赖冲突统统都不需要我们管了。logback框架...

9140

### javascript 基础知识

var bs=Array(); var bs=[1,2,3,4] bs=1 for(i=0;i<bs.length;i++)

6600

14700

15640

6500

### OMAF4CLOUD：启用标准的360°视频创建服务

19400 ## 年度创作总结 领取年终奖励 