- Reverse a Single Linked List
# Reverse a singly linked list.
# Input: 1->2->3->4->5->NULL
# Output: 5->4->3->2->1->NULL
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
curr = head #当前处理节点
head = head.next #当前节点自前往后
curr.next = prev #当前节点指向反向
prev = curr #当前节点处理完毕 作为prev
return prev #最后一个节点处理完毕 为全部反转状态
- Linked List Cycle
# Linked List Cycle
# Given a linked list, determine if it has a cycle in it.
# Use an integer pos tail connects to.
# If pos is -1, then there is no cycle in the linked list.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False
# Utilize O(n) extra space
# def hasCycle(self, head):
# dic = {}
# while head:
# if head in dic:
# return True
# dic[head] = 0
# head = head.next
# return False
- Add Two Numbers
# Add Two Numbers
# given two non-empty linked lists
# digits are stored in reverse order
# Add the two numbers and return it as a linked list.
class Solution:
# def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# addends = l1, l2
# dummy = end = ListNode(0)
# carry = 0
# while addends or carry:
# carry += sum(a.val for a in addends)
# addends = [a.next for a in addends if a.next]
# end.next = end = ListNode(carry % 10)
# carry //= 10
# return dummy.next
def addTwoNumbers(self, l1, l2):
dummy = cur = ListNode(0)
carry = 0
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
cur.next = ListNode(carry%10)
cur = cur.next
carry //= 10
return dummy.next
4.Add Two Numbers II
# 445. Add Two Numbers II
# Add the two numbers and return it as a linked list.
class Solution(object):
def addTwoNumbers(self, l1, l2):
s1 = 0
s2 = 0
while l1: s1 *= 10; s1 += l1.val; l1 = l1.next
while l2: s2 *= 10; s2 += l2.val; l2 = l2.next
s3 = s1 + s2
tail = None
head = None
while s3 > 0: head = ListNode(s3 % 10); head.next = tail; tail = head; s3 //= 10
return head if head else ListNode(0)
5.Merge Two Sorted Lists
# Merge Two Sorted Lists
# Input: 1->2->4, 1->3->4
# Output: 1->1->2->3->4->4
class Solution:
# iteratively
def mergeTwoLists(self, l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
- Merge k Sorted Lists
# 23. Merge k Sorted Lists
# Merge k sorted linked lists
# return it as one sorted list.
class Solution:
def mergeKLists(self, lists):
if not lists: return
if len(lists) == 1: return lists[0]
mid = len(lists)//2
l = self.mergeKLists(lists[:mid])
r = self.mergeKLists(lists[mid:])
return self.merge(l, r)
def merge(self, l, r):
dummy = cur = ListNode(0)
while l and r:
if l.val < r.val:
cur.next = l
l = l.next
else:
cur.next = r
r = r.next
cur = cur.next
cur.next = l or r
return dummy.next
- Intersection of Two Linked Lists
Intersection of Two Linked Lists
# If two linked lists have intersection, we can find two observations:
# They must have same nodes after the intersection point.
# L1+L2 must have same tail from the intersection point as L2 + L1. For example,
# L1 = 1,2,3
# L2 = 6,5,2,3
# L1+L2 = 1,2,3,6,5,2,3
# L2+L1 = 6,5,2,3,1,2,3
# To implement L1+L2 as well as L2+L1, we can simply jump to another list's head
# after traveling through certain list.
# But, you need to notice that if the two lists have no intersection at all,
# you should stop after you've already checked L1+L2, so we need a flag jumpToNext to ensure we only traverse L1 + L2 once.
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ptA, ptB, jumpToNext = headA, headB, False
while ptA and ptB:
if ptA == ptB:
return ptA
ptA, ptB = ptA.next, ptB.next
if not ptA and not jumpToNext:
ptA, jumpToNext = headB, True
if not ptB:
ptB = headA
return None
- Copy List with Random Pointer
# 138. Copy List with Random Pointer
class Solution:
def copyRandomList(self, head):
if not head: return
# copy nodes
cur = head
while cur:
nxt = cur.next
cur.next = RandomListNode(cur.label)
cur.next.next = nxt
cur = nxt
# copy random pointers
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# separate two parts
second = cur = head.next
while cur.next:
head.next = cur.next
head = head.next
cur.next = head.next
cur = cur.next
head.next = None
return second
# # using dictionary
# def copyRandomList(self, head):
# if not head:
# return
# cur, dic = head, {}
# # copy nodes
# while cur:
# dic[cur] = RandomListNode(cur.label)
# cur = cur.next
# cur = head
# # copy random pointers
# while cur:
# if cur.random:
# dic[cur].random = dic[cur.random]
# if cur.next:
# dic[cur].next = dic[cur.next]
# cur = cur.next
# return dic[head]
