206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

Feel free to give this a go and send me your solution. Find me on GitHub here.

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution

Approach

OK, linked lists. First we have to remember that a linked list is a series of connected nodes where the next item in the list is pointed to from the previous. A node has been defined for us already as below:

public class ListNode 
{
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) 
    {
        this.val = val;
        this.next = next;
    }
}

So what we need to do is point to the previous node instead of the next node for each node.

My Attempts

I think this is easier to visualise than it is to explain. Talking about this gets confusing very quickly. The basics are the previous node gets pointed to by the current node, then we look at the next node to point to current.

p = previous, c = current, n = next

1 -> 2 -> 3 -> 4 -> 5
p    c    n
1 <- 2 -> 3 -> 4 -> 5
     p    c    n
1 <- 2 <- 3 -> 4 -> 5
          p    c    n
1 <- 2 <- 3 <- 4 -> 5
               p    c    n
1 <- 2 <- 3 <- 4 <- 5
                    p    c    n

while:
    current is not null
    current node point to previous node
    current point to next
    next node is current previously pointed to

My solution in C#:

You can find my solution here on my GitHub or check out the code below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution 
{
    public ListNode ReverseList(ListNode head) 
    {
        if (head is null || head.next is null)
        {
            return head;
        }

        ListNode previous = head;
        ListNode? current = head.next;
        previous.next = null;
        while (current != null)
        {
            ListNode? next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }
}

First we do the standard check to make sure we actually have a list to reverse on. If this is null or has nothing to point to in next then we just return the given head; which couple potentially be null.

We’re using a similar solution to last week to tackle this linked list. We’re initialising two pointers to track our current positions in the linked list: current and previous. We’re pointing previous to null, as the new tail of the list this should point to nothing.

We loop through the nodes while we have one. When current is null is means there was nothing else left to point to in the list.

We have our swapping logic as we visualised earlier. The tricky part was making sure to keep track of the next node. If we didn’t then we would have lost all references to the next node when we set current.next = previous. and all would be lost.

We need to make sure to return the previous node at the end here. Following our logic above you can see that the current will eventually end up null as thats our loop termination condition we keep trying to look for the next node in the list and when there is none then we should be done.

Complexity

Because our solution iterates over our linked list just the once this is a linear / O(n) solution. We go from the start to the end of the linked list just once and swap the node pointer while we’re at it.

Our space complexity is O(1) because the only extra memory we allocate is the variables for the node pointers, we don’t create another list.