Code Interview [Linked List]
Here’s my conclusion about popular linked list coding questions!
Share with all of you!

Part 1. Reverse Linked List
1.1 [Easy] Reverse Linked List [Next+Pre pointers]
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
while head:
nxt = head.next
head.next = pre
pre = head
head = nxt
return pre # Nodes before pre are reversedTakeaways:
- Next+Pre pointers (Use
nextto save the next node, usepreto point to the previous node)
1.2 [Medium] Reverse linked List 2
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
#create dummy node
dummy = ListNode(0)
dummy.next = head
pre_start = dummy
diff = n - m
#Use "pre_start" point to the position before start
while m > 1:
pre_start = pre_start.next
m -= 1
#Set nodes after "pre_start" as None(Part 1)
start = pre_start.next
pre_start.next = None
end = start
#Locate the position at the "end" position
while diff > 0:
end = end.next
diff -= 1
#Set nodes after "end" as None(Part 3)
nxt_end = end.next
end.next = None
#Reverse relevant part from m to (Part 2)
start2 = start
pre = None
while start:
nxt = start.next
start.next = pre
pre = start
start = nxt
#New List is part1 + part2(reversed) + part3
pre_start.next = pre
start2.next = nxt_end
return dummy.nextTakeaways:
- Break off a linked list(set
nextas None, sincenextdetermined the relationships between nodes) - Next+Pre pointers to reverse the linked list
- Connect two linked list(also use
next(relationship between nodes)to do so) - Dummy node(It’s important when you need to change the structure of the linked list)
1.3 [Medium] Swap nodes in pairs
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
#Special case
if not head or not head.next:
return head
#Reverse in pairs
dummy = ListNode(0)
p = dummy
while head and head.next:
temp = head.next
head.next = temp.next
temp.next = head
p.next = temp
head = head.next
p = temp.next
return dummy.next
#rename head.next
#break head with head.next and connect head to head.next.next
#break head.next with head.next.next and connect head.next to head (reversed)
#connect pointer p to reversed head(previous head.next)
#move head pointer to head.next(previous head.next.next)
#move pointer to head.next(previous head)Takeaways:
- Next+Previous pointers (next pointer is
head.next, the current pointer ishead, the previous pointer isp). - Remember the position of pointers after changing relative locations.
Part 2. Delete
2.1 [Easy] Remove linked list elements(With head)
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummy = TreeNode(0)
dummy.next = head
pre = dummy
#If find head should be deleted, use pre pointer to pass it.
while head:
if head.val == val:
pre.next = head.next
head = pre.next
else:
pre = pre.next
head = head.next
return dummy.nextTakeaways:
- (Basic) Remove node using its previous node.
2.2 [Easy] Delete node in a linked list(Without head)
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next#Since it need to do it in-place, copying node.next to node then delete node.next.
Takeaways:
- In-place deleting (small trick)
2.3 [Easy] Remove duplicates from sorted list (distinct nodes)
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
#Special case
if not head:
return head
#Two adjacent pointers
p1 = head
p2 = head.next
while p2:
if p1.val == p2.val:
p1.next = p2.next
p2 = p1.next
else:
p1 = p1.next
p2 = p2.next
return head#If duplicated, remove latter pointer node and the node after as new latter pointer.
#If not duplicated, former and latter pointers will move until no more nodes.
Takeaways:
- Two pointers (same direction + adjacent)
- (Basic) Remove node using its previous node.
2.4[Medium] Remove duplicated from sorted list 2(only distinct nodes)
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
dummy = pre = ListNode(0)
dummy.next = head while head and head.next:
if head.val == head.next.val:
while head and head.next and \
head.val == head.next.val:
head = head.next
pre.next = head.next
head = head.next
else:
pre = pre.next
head = head.next
return dummy.next
# If find duplcates, head keep walking until distinct node appears.
# Nodes before pre are all showing at most once before.
Takeaways:
- Know the position of
preandpre.next
2.5[Medium] Remove Nth node from the end of the list
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
""" slow = fast = res = ListNode(0)
slow.next = head
while n > 0:
fast = fast.next
n -= 1
while fast and fast.next:
slow = slow.next
fast = fast.next #slow.next is target(need to remove)
slow.next = slow.next.next
return res.next
Takeaways:
- Two pointers(Fast-slow pointers to locate the position before
targetnode) - Dummy node
Part 3. Cycle
Method: Fast+Slow pointers
Detect cycle: Both start from head, fast moves 2 steps each time, slow moves 1 time each time. If they meet, a cycle exists.
Find cycle enter location: (keep the position of meeting from Detect cycle), use another pointer res moving from head with 1 step each time, also move slow/fast(same location now) with 1 step each time. The meeting point of res and slow/fast is enter location.
3.1 [Easy] Linked list cycle (Detect cycle)
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False3.2 [Medium] Linked list cycle 2(Enter location)
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = fast = res = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
break
else:
return None
while res is not slow:
res = res.next
slow = slow.next
else:
return resPart 4. Sort + Merge
4.1 [Medium] Sort List(Merge sort)
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
#merge sort---divide
#recursion output
if head is None or head.next is None:
return head
#find mid point(slow-fast pointers)
s, f = ListNode(0), ListNode(0)
s.next, f.next = head, head
while f.next and f.next.next:
s = s.next
f = f.next.next
right = self.sortList(s.next)
#cut
s.next = None
left = self.sortList(head)
return self.merge(left, right)
def merge(self, l, r):
#merge into l list, so l should be the smallest
if l.val >= r.val:
l, r = r, l
new_head = l
pre = l
l = l.next
#intert node in linked list(the position of l is not changed but pre changed)
while l and r:
if l.val <= r.val:
pre = pre.next
l = l.next
else:
lnxt = pre.next
pre.next = r
rnxt = r.next
r.next = lnxt
r = rnxt
pre = pre.next
pre.next = l or r
return new_headTakeaways:
- Divide and conquer(recursion)
- Midpoint of linked list (Fast-slow pointers)
- Merge two linked list in-place(notice the position after merging)
Will updating merge part in the following week.
