链表高频题
原创
总结：所有链表题目都做过而且都Accept了，不排除有些是抄的。。leet, leet-cn
高频共12道，另外加了两道(reverse at k和环形2)
链表定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None基础题
206. 反转链表
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLFollow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution - 递归
class Solution:
def reverseList(self, head: ListNode):
if not head or not head.next: return head
next_node = head.next
res = self.reverseList(next_node)
next_node.next = head
head.next = None
return resSolution - 迭代**
class Solution:
def reverseList(self, head: ListNode):
pre = None
curr = head
while curr:
pre, curr.next, curr = curr, pre, curr.next
return preReference 超级好
重难点 (M->H)
138. 复制带随机指针的链表
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':
if not head: return None
node = head
di = {}
while node:
di[node] = Node(node.val, None, None)
node = node.next
node= head
while node:
di[node].next = di.get(node.next)
di[node].random = di.get(node.random)
node= node.next
return di[head]遍历两遍同时On哈希的空间
待优化：遍历一遍并常数空间cost
21. 合并两个有序链表
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->4Solution-递归
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 l2Solution-迭代
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.next23. 合并K个排序链表
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->6Solution
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知道分支的思路，但mergeKLists是抄的，不知道怎么写分治的code
25. K 个一组翻转链表
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:
Given this linked list: 1->2->3->4->5
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
class Solution(object):
def reverseKGroup(self, head, k):
if not head or not head.next: return head
cur = head
cnt = 0
while cur and cnt < k:
cur = cur.next
cnt += 1
if cnt == k:
cur = self.reverseKGroup(cur, k)
while cnt:
head.next, head, cur = cur, head.next, head
cnt -= 1
head = cur
return head双指针技巧
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:
slow, fast = head, head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast: return True
return False142. 环形链表 II
Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1Solution
class Solution:
def detectCycle(self, head: ListNode):
slow, fast = head, head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast: break
else:
return None
while head != fast:
head, fast = head.next, fast.next
return head160. 相交链表
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):
def getIntersectionNode(self, headA, headB):
if not headA or not headB: return None
from collections import defaultdict
di = defaultdict(ListNode)
while headA:
di[headA] = 1
headA = headA.next
while headB:
if headB in di: return headB
headB = headB.next
return NoneDict做法，还可以用双指针
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:
if not head: return None
slow, fast = head, head
for _ in range(n):
fast = fast.next
if not fast: return head.next
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return head快指针先走n步
其他
234. 回文链表
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: falseExample 2:
Input: 1->2->2->1
Output: trueFollow up: Could you do it in O(n) time and O(1) space?
Solution
class Solution(object):
def isPalindrome(self, head):
if not head: return True
slow, fast = head, head.next
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 True328. 奇偶链表
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->NULLExample 2:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULLSolution
class Solution(object):
def oddEvenList(self, head):
if not head or not head.next: return head
odd = head
even = even_head = head.next
while odd and even and even.next:
odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next
odd.next = even_head
return head2. 两数相加
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.next148. 排序链表
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->4Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5Solution
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
mid, slow.next = slow.next, None
left, right = self.sortList(head), self.sortList(mid)
# 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.nextmergesort
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。