Introduction

A singly linked list is a collection of nodes where each node is charcterized by a value val and a reference next, which is a pointer to the next node in the sequence. Implementing such a data structure is easy, as the following Python class ListNode demonstrates.

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next

Fundamental operations on singly linked-lists:

In the following, we are going to review fundamental operations on linked lists. This includes reversing, sorting, or removing elements from a single list as well as merging different lists or determining their intersection.

Reversing a list

In a singly linked list, reversal is one of the fundamental operations.

Reversing a list follows a straightforward procedure that relies on three pointers: the previous node prev, the current node curr and the next node next.

 1def reverseList(self, head: ListNode) -> ListNode:
 2    prev = None
 3    curr = head
 4
 5    while curr is not None:
 6        next = curr.next
 7        curr.next = prev
 8
 9        prev = curr
10        curr = next

Removing all elements with value k from a linked list

The next fundamental operation removes all nodes with a given value from the linked list.

This operation is trivial, as we simpy skip the connection from the current node curr to curr.next, if the latter node has value k.

 1def removeElements(self, head: ListNode, k) -> ListNode:
 2    dummy = ListNode()
 3    dummy.next, curr = head, dummy
 4
 5    while curr.next is not None:
 6        if curr.next.val == k:
 7            curr.next = curr.next.next
 8        else:
 9            curr = curr.next
10
11    return dummy.next 

Remove duplicates from a sorted list

Removing duplicates is very similar to removing all nodes with a given value.

The key lies in the second while loop.

 1def deleteDuplicates(self, head: ListNode) -> ListNode:
 2
 3    cur = head
 4
 5    while cur:
 6        while cur.next and cur.next.val == cur.val:
 7            cur.next = cur.next.next
 8        cur = cur.next
 9
10    return head

Sorting all elements in a linked list

The next fundamental operation sorts a linked list.

This operation is more challenging and relies on a recursion. We begin by splitting our linked list recursively in a left and right half and merge the sorted result.

 1def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 2
 3    if not head or not head.next:
 4            return head
 5        
 6    left = head
 7    right = self.getMid(head)
 8    tmp = right.next
 9    right.next = None
10    right = tmp
11    
12    left = self.sortList(left)
13    right = self.sortList(right)
14    
15    return self.merge(left, right)
16    
17def getMid(self, head):
18    slow = head
19    fast = head.next
20    
21    while fast and fast.next:
22        slow = slow.next
23        fast = fast.next.next
24    return slow
25
26def merge(self, list1, list2):
27    newHead = tail = ListNode()
28    while list1 and list2:
29        if list1.val > list2.val:
30            tail.next = list2
31            list2 = list2.next
32        else:
33            tail.next = list1
34            list1 = list1.next
35        tail = tail.next
36    
37    tail.next = list1 or list2
38    
39    return newHead.next

Merge two sorted lists into a sorted list

As in the previous example, merging two sorted lists is trivial.

The code directly corresponds to the merge() function in the previous example.

 1def mergeTwoLists(self, list1, list2) -> ListNode:
 2
 3    dummy = cur = ListNode()
 4
 5    while list1 and list2:
 6        if list1.val < list2.val:
 7            cur.next = list1
 8            list1 = list1.next
 9        else:
10            cur.next = list2
11            list2 = list2.next
12        cur = cur.next
13        
14    cur.next = list1 or list2
15    return dummy.next

Determine the intersection of two linked lists

Assume that we are given the heads of two linked lists, headA and headB. If the linked lists intersect, we want to know at which node.

We can make the following key observation: Regardless of whether the linked lists intersect, moving from headA to the tail and then from headB to the tail requires the same number of steps as moving from headB to the tail and then from headA to the tail.

Assume that we have two pointers a and b to the headAand headB, respectively. Pointer a (b) starts at headA (headB) and moves to the tail, before starting from headB (headA) to move to the tail once again. If we move both pointers one step at a time, then they will either:

• both be None (after starting from both heads of non-intersecting lists).
• meet at the intersection after starting from the first head, if the number of nodes before the intersection is equal.
• meet at the intersection after starting from the second head, if the number of nodes before the intersection is unequal.

This is exactly what the following code does:

 1def getIntersectionNode(self, headA, headB) -> ListNode:
 2
 3    if headA is None or headB is None:
 4        return None
 5
 6    a = headA
 7    b = headB
 8
 9    while a is not b:
10        a = headB if a is None else a.next
11        b = headA if b is None else b.next
12
13    return a

Remove the n-th element from the end of the list

We use two pointers: slow and fast, where the latter is given a headstart of n

 1def removeNthFromEnd(self, head: ListNode, n: int) -> Optional[ListNode]:
 2
 3    fast, slow = head, head
 4
 5    for _ in range(n):
 6        fast = fast.next
 7    if not fast:
 8        return head.next
 9    
10    while fast.next is not None:
11        fast, slow = fast.next, slow.next
12    slow.next = slow.next.next
13
14    return head

Rotating the list to the right by k places

The idea is to first count the length of the list and introduce a cycle that links tail to head. As k may be larger than length, we update k = k % length. All that remains is to move length - k - 1 steps from the head to break the cycle.

 1def rotateRight(self, head: ListNode, k: int) -> ListNode:
 2
 3    if not head:
 4        return None
 5
 6    tail = head
 7    length = 1
 8    while tail.next is not None:
 9        tail = tail.next
10        length += 1
11
12    k = k % length
13    tail.next = head
14
15    temp = head
16    for _ in range(length - k - 1):
17        temp = temp.next
18
19    result = temp.next
20    temp.next = None
21
22
23    return result

Cycle detection in singly linked lists

Let head be the root element of singly linked list of finite size. We want to know if there is a cycle in the linked list and at which node (if any) it occurs.

This problem has a very elegant solution known as Floyd’s cycle detection algorithm (also known as tortoise and hare algorithm).

 1def detectCycle(self, head: ListNode) -> Optional[ListNode]:
 2
 3    slow, fast = head, head
 4
 5    while fast and fast.next:
 6        slow = slow.next
 7        fast = fast.next.next
 8        if slow == fast:
 9            slow = head
10            while slow != fast:
11                slow = slow.next
12                fast = fast.next
13            return slow
14    return None

This solution may seem counterintuituive. More precisely, a question may be why this algorithm is guaranteed to always work, irrespective of the number of nodes before the cycle, the duration of the cycle, or the position in the cycle where slow and fast meet?

Let $f$ and $s$ be the number of nodes traversed by fast and slow, respectively. We know that $f = 2s$ must hold when slow and fast meet for the first time. Additionally, let $n_{start}$ and $n_{cycle}$ be the number of nodes required to reach the start of the cycle and the duration of the cycle, respectively. Finally, define $n_{meet}$ as the number of nodes from the start necessary to reach the meeting point of slow and fast.

We can derive the following system of equations:

Inserting $f = 2s$ we receive:

Therefore, the distance $n_{start}$ to travel from the head to the start of the cycle is identical to the distance required to complete the cycle when starting at $n_{meet}$.

Conclusion

Further challenges can easily be addressed by relying on the presented building blocks! 🚀