刷题总结 - Linked List

In this card, we are going to introduce another data structure - Linked List.

Similar to the array, the linked list is also a linear data structure. Here is an example:

As you can see, each element in the linked list is actually a separate object while all the objects are linked together by the reference field in each element.

There are two types of linked list: singly linked list and doubly linked list. The example above is a singly linked list and here is an example of doubly linked list:

We will introduce more in later chapters. After this card, you will:

• Understand the structure of singly linked list and doubly linked list;
• Implement traversal, insertion, deletion in a singly or doubly linked list;
• Analyze the complexity of different operations in a singly or doubly linked list;
• Use two-pointer technique (fast-pointer-slow-pointer technique) in the linked list;
• Solve classic problems such as reverse a linked list;
• Analyze the complexity of the algorithms you designed;
• Accumulate experience in designing and debugging.

Introduction - Singly Linked List

Each node in a singly-linked list contains not only the value but also a reference field to link to the next node. By this way, the singly-linked list organizes all the nodes in a sequence.

Here is an example of a singly-linked list:

The blue arrows show how nodes in a singly linked list are combined together.

Node Strucutre

Here is the typical definition of a node in a singly-linked list:

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

In most cases, we will use the head node (the first node) to represent the whole list.

Operations

Unlike the array, we are not able to access a random element in a singly-linked list in constant time. If we want to get the ith element, we have to traverse from the head node one by one. It takes us $O(N)$ time on average to visit an element by index, where N is the length of the linked list.

For instance, in the example above, the head is the node 23. The only way to visit the 3rd node is to use the next field of the head node to get to the 2nd node (node 6); Then with the next field of node 6, we are able to visit the 3rd node.

You might wonder why the linked list is useful though it has such a bad performance (compared to the array) in accessing data by index. We will introduce the insert and delete operations in next two articles and you will realize the benefit of the linked list.

After that, we provide an exercise for you to design your own singly linked list.

Add Operation - Singly Linked List

If we want to add a new value after a given node prev, we should:

1. Initialize a new node cur with the given value;

2. Link the next field of cur to prev's next node next;

3. Link the next field in prev to cur.

Unlike an array, we don’t need to move all elements past the inserted element. Therefore, you can insert a new node into a linked list in $O(1)$ time complexity, which is very efficient.

An Example

Let's insert a new value 9 after the second node 6.

We will first initialize a new node with value 9. Then link node 9 to node 15. Finally, link node 6 to node 9.

After insertion, our linked list will look like this:

Add a Node at the Beginning

As we know, we use the head node head to represent the whole list.

So it is essential to update head when adding a new node at the beginning of the list.

1. Initialize a new node cur;
2. Link the new node to our original head node head.
3. Assign cur to head.

For example, let's add a new node 9 at the beginning of the list.

1. We initialize a new node 9 and link node 9 to current head node 23.

2. Assign node 9 to be our new head.

public void push(int new_data) {
    /* 1 & 2: Allocate the Node &
              Put in the data*/
        Node new_node = new Node(new_data);
        /* 3. Make next of new Node as head */
        new_node.next = head;
        /* 4. Move the head to point to new Node */
        head = new_node;
    }

What about adding a new node at the end of the list? Can we still use similar strategy?

Add a node after a given node

public void insertAfter(Node prev_node, int new_data) {
        /* 1. Check if the given Node is null */
        if (prev_node == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }
    /* 2. Allocate the Node &
       3. Put in the data*/
        Node new_node = new Node(new_data);
        /* 4. Make next of new Node as next of prev_node */
        new_node.next = prev_node.next;
        /* 5. make next of prev_node as new_node */
        prev_node.next = new_node;
    }

Add a node at the end

Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

public void append(int new_data) {
    /* 1. Allocate the Node &
       2. Put in the data
       3. Set next as null */
        Node new_node = new Node(new_data);
    /* 4. If the Linked List is empty, then make the new node as head */
        if (head == null) {
            head = new Node(new_data);
            return;
        }
    /* 4. This new node is going to be the last node, so make next of it as null */
        new_node.next = null;
        /* 5. Else traverse till the last node */ // Traverse 很重要！！！
        Node last = head;
        while (last.next != null)
            last = last.next;
        /* 6. Change the next of last node */
        last.next = new_node;
        return;
    }

Delete Operation - Singly Linked List

If we want to delete an existing node cur from the singly linked list, we can do it in two steps:

1. Find cur's previous node prev and its next node next;

Link prev to cur's next node next.

In our first step, we need to find out prev and next. It is easy to find out next using the reference field of cur. However, we have to traverse the linked list from the head node to find out prev which will take $O(N)$ time on average, where $N$ is the length of the linked list. So the time complexity of deleting a node will be $O(N)$.

The space complexity is $O(1)$ because we only need constant space to store our pointers.

/* Given a key, deletes the first occurrence of key in linked list */
    void deleteNode(int key) {
        // Store head node
        Node temp = head, prev = null;
        // If head node itself holds the key to be deleted !!!
        if (temp != null && temp.data == key) { // 要检查最后一个，所以是 temp != null
            head = temp.next; // Changed head
            return;
        }
        // Search for the key to be deleted, keep track of the previous node as we need to change temp.next
        while (temp != null && temp.data != key) { // prev 是 key 之前的，temp 是 key 的！！！
            prev = temp;
            temp = temp.next;
        }
        // If key was not present in linked list!!!
        if (temp == null) return;
        // Unlink the node from linked list
        prev.next = temp.next;
    }

An Example

Let's try to delete node 6 from the singly linked list above.

1. Traverse the linked list from the head until we find the previous node prev which is node 23

2. Link prev (node 23) with next (node 15)

Node 6 is not in our singly linked list now.

Delete the First Node

If we want to delete the first node, the strategy will be a little different.

As we mentioned before, we use the head node head to represent a linked list. Our head is the black node 23 in the example below.

If we want to delete the first node, we can simply assign the next node to head. That is to say, our head will be node 6 after deletion.

The linked list begins at the head node, so node 23 is no longer in our linked list.

What about deleting the last node? Can we still use similar strategy?

Question - Design Linked List

class MyLinkedList {

    private int val;
    private MyLinkedList next;

    public MyLinkedList() {
        val = -1;
    }

    public int get(int index) {
        if (index < 0) {
            // invalid index
            return -1;
        } else {
            MyLinkedList node = this;
            int p = 0;
            while (p++ < index) {
                node = node.next;
                if (node == null) {
                    // reached the end of the list before reaching the index
                    return -1;
                }
            }
            return node.val;
        }
    }

    public void addAtHead(int val) {
        if (this.val == -1) {
            // test if this is the first value being added
            this.val = val;
        } else {
            // create a clone of the head,
            // modify the head value
            // make the new head point to the clone of the old head
            MyLinkedList clone = new MyLinkedList();
            clone.val = this.val;
            clone.next = this.next;
            this.val = val;
            this.next = clone;
        }

    }

    public void addAtTail(int val) {
        if (this.val == -1) {
            this.val = val;
        } else {
            MyLinkedList tailNode = this;
            while (tailNode.next != null) {
                // skip through nodes until tailNode.next is null
                tailNode = tailNode.next;
            }
            // create new node at the end
            tailNode.next = new MyLinkedList();
            tailNode.next.val = val;
        }
    }

    public void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
        } else if (index > 0) {
            MyLinkedList pNode = this, cNode = this.next;
            int i = 1;
            while (i < index && cNode != null) {
                // step through until we reach the index
                // or until we reach the end of the list
                pNode = cNode;
                cNode = cNode.next;
                i++;
            }
            if (i == index && pNode.val != -1) {
                // add node between the prev and current node.
                MyLinkedList newNode = new MyLinkedList();
                newNode.val = val;
                newNode.next = pNode.next;
                pNode.next = newNode;

            }
        }
    }

    public void deleteAtIndex(int index) {
        MyLinkedList pNode = this, cNode = this.next;
        if (index == 0) {
            int length = 0;
            while (cNode != null) {
                // shift node values left
                pNode.val = cNode.val;
                pNode = cNode;
                cNode = cNode.next;
                length++;
            }
            // delete last node
            deleteAtIndex(length);
        } else {
            int i = 1;
            while (i < index && cNode != null) {
                // step through until we reach the index
                // or until we reach the end of the list
                pNode = cNode;
                cNode = cNode.next;
                i++;
            }
            if (i == index && cNode != null) {
                // make previous node's "next" skip over the node we're deleting
                pNode.next = cNode.next;
            }
        }
    }

}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

Design Singly Linked List - Solution

Two-Pointer in Linked List

Let's start with a classic problem:

Given a linked list, determine if it has a cycle in it.

You might have come up with the solution using the hash table. But there is a more efficient solution using the two-pointer technique. Try to think it over by yourself before reading the remaining content.

Imagine there are two runners with different speed. If they are running on a straight path, the fast runner will first arrive at the destination. However, if they are running on a circular track, the fast runner will catch up with the slow runner if they keep running.

1. If there is no cycle, the fast pointer will stop at the end of the linked list.

2. If there is a cycle, the fast pointer will eventually meet with the slow pointer.

So the only remaining problem is:

What should be the proper speed for the two pointers?

It is a safe choice to move the slow pointer one step at a time while moving the fast pointer two steps at a time. For each iteration, the fast pointer will move one extra step. If the length of the cycle is M, after M iterations, the fast pointer will definitely move one more cycle and catch up with the slow pointer.

What about other choices? Do they work? Would they be more efficient?

Question - Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
        slow = slow.next;
        fast = fast.next.next;
        }
        return true;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            if (slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}

Question - Linked List Cycle II

快慢指针解决成环问题

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Question - Intersection of Two Linked Lists

快慢指针解决相交问题

Write a program to find the node at which the intersection of two singly linked lists begins.

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        //if a & b have different len, then we will stop the loop after second iteration
        while (a != b) {
            //for the end of first iteration, we just reset the pointer to the head of another linkedlist
            if (a == null) {
                a = headB;
                continue;
            }##
            if (b == null) {
                b = headA;
                continue;
            }
            a = a.next;
            b = b.next;
        }
        return a;
    }
}

Question - Remove Nth Node From End of List

快慢指针解决从末尾开始的问题

Given a linked list, remove the n-th node from the end of list and return its head.

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode slow = start, fast = start;

        // Move fast in front so that the gap between slow and fast becomes n
        // 因为 slow 要变成倒数第 n 个的前一个，所以 fast 空出 n + 1 的位置！！！
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        // Move fast to the end, maintaining the gap
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // Skip the desired node
        slow.next = slow.next.next;
        return start.next;
    }
}

Summary - Two-Pointer in Linked List

Here we provide a template for you to solve the two-pointer problem in the linked list.

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) { // 会用到 fast.next，所以需要确保 fast.next != null！！！
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

Tips

It is similar to what we have learned in an array. But it can be trickier and error-prone. There are several things you should pay attention:

1. Always examine if the node is null before you call the next field.

Getting the next node of a null node will cause the null-pointer error. For example, before we run fast = fast.next.next, we need to examine both fast and fast.next is not null.

2. Carefully define the end conditions of your loop.

Run several examples to make sure your end conditions will not result in an endless loop. And you have to take our first tip into consideration when you define your end conditions.

Complexity Analysis
It is easy to analyze the space complexity. If you only use pointers without any other extra space, the space complexity will be $O(1)$. However, it is more difficult to analyze the time complexity. In order to get the answer, we need to analyze how many times we will run our loop.

In our previous finding cycle example, let's assume that we move the faster pointer 2 steps each time and move the slower pointer 1 step each time.

1. If there is no cycle, the fast pointer takes N/2 times to reach the end of the linked list, where N is the length of the linked list.
2. If there is a cycle, the fast pointer needs M times to catch up the slower pointer, where M is the length of the cycle in the list.

Obviously, M <= N. So we will run the loop up to N times. And for each loop, we only need constant time. So, the time complexity of this algorithm is $O(N)$ in total.

Analyze other problems by yourself to improve your analysis skill. Don't forget to take different conditions into consideration. If it is hard to analyze for all situations, consider the worst one.

Reverse Linked List

Let's start with a classic problem:

Reverse a singly linked list.

One solution is to iterate the nodes in original order and move them to the head of the list one by one. It seems hard to understand. We will first use an example to go through our algorithm.

Algorithm Overview

Let's look at an example:

Keep in mind that the black node 23 is our original head node.

1. First, we move the next node of the black node, which is node 6, to the head of the list:

2. Then we move the next node of the black node, which is node 15, to the head of the list:

3. The next node of the black node now is null. So we stop and return our new head node 15.

In this algorithm, each node will be moved exactly once.

Therefore, the time complexity is $O(N)$, where N is the length of the linked list. We only use constant extra space so the space complexity is $O(1)$.

This problem is the foundation of many linked-list problems you might come across in your interview. If you are still stuck, our next article will talk more about the implementation details.

There are also many other solutions. You should be familiar with at least one solution and be able to implement it.

Question - Reverse Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution { // recurisve
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode secondHead = head.next;
        ListNode newHead = reverseList(head.next);
        secondHead.next = head;
        head.next = null;
        return newHead;

    }
}

//    思路：
//            1. 将 head.next 取出来；
//            2. 放置于 currentHead 之前；
//            3. 将 currentHead 更新。
class Solution { // iteritive
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode currentHead = head;
        while (head.next != null) {
            ListNode ne = head.next;
            head.next = head.next.next;
            ne.next = currentHead;
            currentHead = ne;
        }
        return currentHead;
    }
}

Reverse Linked List - Solution

In this article, we will talk more about details of our algorithm to reverse the linked list.

In the solution we mentioned previously, there are two nodes which we should keep track of: the original head node and the new head node.

Therefore, we need to use two pointers in one linked list at the same time. One pointer head always points at our original head node while another pointer curHead always points at our newest head node.

Let's focus on a single step (the 2nd step in the previous article). Our goal is to move the next node of head, which is 15, to the head of the list.

1. First, we use a temporary pointer p to indicate the next node of the head node. And link the next field of head to the next field of p.

2. Then, we link the next field of p to the curHead.

3. Now our linked list actually looks like the picture below. And we set curHead to be p.

By this way, we successfully move node 15 to the head of the list. And we can repeat this process until the next node of head is null.

Question - Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode prev = fakeHead, curr = head;
        while (curr != null) {
            if (curr.val == val) {
                prev.next = prev.next.next;
            }
            else prev = prev.next;
            curr = curr.next;
        }
        return fakeHead.next;
    }
}