leetcode 链表专题
- 反转链表
三指针 + 递归
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverselist(head: Optional[ListNode], prev: Optional[ListNode]):
if head is None:
return prev
else:
next = head.next
head.next = prev
return reverselist(next, head)
return reverselist(head, None)
prev, next = None, None
#使用三指针写法 回收内存
while head:
next, head.next, prev = head.next, prev, head
head = next
del head, next
return prev
- 合并两个有序链表（归并排序）
双指针迭代 + 递归链表
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# normal 两个链表叠加 merge
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
# 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
tail.next = l1 if l1 is not None else l2
return dummy.next
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val > l2.val:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
else:
l1.next = self.mergeTwoLists(l2, l1.next)
return l1
- 两两交换链表中的节点
顺序遍历
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = head
if p and p.next:
s = p.next
p.next, s.next = s.next, p
head = s
while p.next and p.next.next:
s = p.next
p.next = s.next
s.next = p.next.next
p.next.next = s
p = s
return head
- 相交链表
长度加和遍历 + set查表
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
# l1, l2 = headA, headB
# while l1 is not l2:
# l1 = l1.next if l1 else headB
# l2 = l2.next if l2 else headA
# return l1
# 2
lset = set()
l1, l2 = headA, headB
while l1:
lset.add(l1)
l1 = l1.next
while l2:
if l2 in lset:
return l2
else:
l2 = l2.next
return l2
- 回文链表
快慢指针 + 反转链表（不还原）
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def reverseList(node: Optional[ListNode]) -> Optional[ListNode]:
if node is None:
return
prev, next = None, node.next
while node:
next = node.next
node.next = prev
prev, node = node, next
return prev
# main function
if head is None or head.next is None:
return True
# 设置快慢指针 -> 截断链表并生成双子链表
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
node = reverseList(slow.next)
slow.next = node
slow = slow.next
while slow:
if head.val != slow.val:
return False
head = head.next
slow = slow.next
return True
- 删除排序链表中的重复元素
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
num_t = None
ptr = head
node = None
while ptr:
if ptr.val != num_t:
num_t = ptr.val
node = ptr
else:
node.next = ptr.next
del ptr
ptr = node.next
return head
- 奇偶链表
双表链接
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 要求O(n)复杂度
if not head:
return
odd_head = head
evenHead, even_head = head.next, head.next
while even_head and even_head.next:
odd_head.next = even_head.next
odd_head = odd_head.next
even_head.next = odd_head.next
even_head = even_head.next
odd_head.next = evenHead
return head
- 排序链表
归并排序 + 自底向上
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# mergesort
def mergesort(headA: Optional[ListNode], headB: Optional[ListNode]) -> ListNode:
dummy= ListNode()
tail = dummy
l1, l2 = headA, headB
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
# main function
dummy = ListNode(next=head)
length = 0
# get the length
node = head
while node:
node = node.next
length += 1
sublength = 1
while sublength < length:
p, c = dummy, dummy.next
while c:
# decide the head1
head1 = c
for _ in range(1, sublength):
if c.next:
c = c.next
else:
break
# decide the head2
head2 = c.next
c.next = None
c = head2
for _ in range(1, sublength):
if c and c.next:
c = c.next
else:
break
# save the next head
succ = None
if c:
succ = c.next
c.next = None
p.next = mergesort(head1, head2)
while p.next:
p = p.next
c = succ
sublength <<= 1
return dummy.next