Code Interview [Linked List]

Mia Li
Mia Li
Sep 6, 2018 · 5 min read

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 reversed

Takeaways:

  • Next+Pre pointers (Use next to save the next node, use pre to 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.next

Takeaways:

  • Break off a linked list(set next as None, since next determined 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 ishead.next, the current pointer ishead , the previous pointer is p ).
  • 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.next

Takeaways:

  • (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 pre and pre.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 target node)
  • 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 False

3.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 res

Part 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_head

Takeaways:

  • 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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade