LeetCode Linked List

[zxw018018]

LeetCode Linked List

Singly Linked List

Node Structure

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

Add Operation

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

Time Complexity O(1)

Delete Operation

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

2. Link prev to cur's next node next.

Time Complexity O(n), space complexity O(1)

707. Design Linked List

1. Initiate a new linked list: represent a linked list using the head node.

private SinglyListNode head;
public MyLinkedList() {
    head = null;
}

2. Traverse the linked list to get element by index.

/** Helper function to return the index-th node in the linked list. */
private SinglyListNode getNode(int index) {
    SinglyListNode cur = head;
    for (int i = 0; i < index && cur != null; ++i) {
        cur = cur.next;
    }
    return cur;
}
/** Helper function to return the last node in the linked list. */
private SinglyListNode getTail() {
    SinglyListNode cur = head;
    while (cur != null && cur.next != null) {
        cur = cur.next;
    }
    return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
    SinglyListNode cur = getNode(index);
    return cur == null ? -1 : cur.val;
}

3. Add a new node.

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
    SinglyListNode cur = new SinglyListNode(val);
    cur.next = head;
    head = cur;
    return;
}

/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
    if (head == null) {
        addAtHead(val);
        return;
    }
    SinglyListNode prev = getTail();
    SinglyListNode cur = new SinglyListNode(val);
    prev.next = cur;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
    if (index == 0) {
        addAtHead(val);
        return;
    }
    SinglyListNode prev = getNode(index - 1);
    if (prev == null) {
        return;
    }
    SinglyListNode cur = new SinglyListNode(val);
    SinglyListNode next = prev.next;
    cur.next = next;
    prev.next = cur;
}

4. Delete a node.

/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
    SinglyListNode cur = getNode(index);
    if (cur == null) {
        return;
    }
    SinglyListNode prev = getNode(index - 1);
    SinglyListNode next = cur.next;
    if (prev != null) {
        prev.next = next;
    } else {
        // modify head when deleting the first node.
        head = next;
    }
}

206. Reverse Linked List

• Let's look at an example:

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.

Doubly Linked List

Node Structure

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

Add Operation

If we want to insert a new node cur after an existing node prev, we can divide this process into two steps:

1. link cur with prev and next, where next is the original next node of prev;

2. re-link the prev and next with cur.

Delete Operation

• If we want to delete an existing node cur from the doubly linked list, we can simply link its previous node prev with its next node next.

707. Design Linked List

1. Initiate a new linked list: represent a linked list using the head node.

private DoublyListNode head;
/** Initialize your data structure here. */
public MyLinkedList() {
    head = null;
}

2. Traverse the linked list to get element by index.

/** Helper function to return the index-th node in the linked list. */
private DoublyListNode getNode(int index) {
    DoublyListNode cur = head;
    for (int i = 0; i < index && cur != null; ++i) {
        cur = cur.next;
    }
    return cur;
}
/** Helper function to return the last node in the linked list. */
private DoublyListNode getTail() {
    DoublyListNode cur = head;
    while (cur != null && cur.next != null) {
        cur = cur.next;
    }
    return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
    DoublyListNode cur = getNode(index);
    return cur == null ? -1 : cur.val;
}

3. Add a new node.

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
    DoublyListNode cur = new DoublyListNode(val);
    cur.next = head;
    if (head != null) {
        head.prev = cur;
    }
    head = cur;
    return;
}

/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
    if (head == null) {
        addAtHead(val);
        return;
    }
    DoublyListNode prev = getTail();
    DoublyListNode cur = new DoublyListNode(val);
    prev.next = cur;
    cur.prev = prev;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
    if (index == 0) {
        addAtHead(val);
        return;
    }
    DoublyListNode prev = getNode(index - 1);
    if (prev == null) {
        return;
    }
    DoublyListNode cur = new DoublyListNode(val);
    DoublyListNode next = prev.next;
    cur.prev = prev;
    cur.next = next;
    prev.next = cur;
    if (next != null) {
        next.prev = cur;
    }
}

4. Delete a node.

/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
    DoublyListNode cur = getNode(index);
    if (cur == null) {
        return;
    }
    DoublyListNode prev = cur.prev;
    DoublyListNode next = cur.next;
    if (prev != null) {
        prev.next = next;
    } else {
        // modify head when deleting the first node.
        head = next;
    }
    if (next != null) {
        next.prev = prev;
    }
}

Comparison

Problems

2. Add Two Numbers

Description

• You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
• You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Analysis

• Create dummy head iterate through two lists.

19. Remove Nth Node From End of List

Description

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

Analysis

• Set two pointers p and q
• Let q go n steps first, then let them go together till the end of the list
• Delete p->next

21. Merge Two Sorted Lists

Description

• Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis

• Compare each pair and link them together.

24. Swap Nodes in Pairs

Description

• Given a linked list, swap every two adjacent nodes and return its head.

Analysis

• Use prev, cur, next pointers.

25. Reverse Nodes in k-Group

Description

• Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
• k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Analysis

• Find nextGroup and do recursion on each nextGroup. The calculation in recursion is done on newNextGroup pointer.

61. Rotate List

Description

• Given a linked list, rotate the list to the right by k places, where k is non-negative.

Analysis

• Find out the length of the list, get the reminder of k.
• Link end to head to create a circle.
• Find out where to unlink the circle to get the link.

82. Remove Duplicates from Sorted List II

Description

• Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Analysis

• Use recursive method to justify whether there is a duplicate or not.

83. Remove Duplicates from Sorted List

Description

• Given a sorted linked list, delete all duplicates such that each element appear only once.

Analysis

• Use prev and cur to iterate through the list.

86. Partition List

Description

• Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
• You should preserve the original relative order of the nodes in each of the two partitions.

Analysis

• Create two list, left list and right list.

92. Reverse Linked List II

Description

• Reverse a linked list from position m to n. Do it in one-pass.
• Note: 1 ≤ m ≤ n ≤ length of list.

Analysis

• Find the head of the reverse begins and do every reverse.

138. Copy List with Random Pointer

Description

• A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
• Return a deep copy of the list.

Analysis

• Use recursion and create a HashMap to store relationship between head and node.

141. Linked List Cycle

Description

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

Analysis

• Use two pointers. One is slow, the other one is fast.

142. Linked List Cycle II

Description

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

Analysis

1. Find intersection
2. From head and intersection to find the node where the cycle begins.
   time O(n), space O(1)

143. Reorder List

Description

• Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
• You may not modify the values in the list's nodes, only nodes itself may be changed.

Analysis

• Find the middle point, split it up and reverse the right part. Then link them together.

146. LRU Cache

Description

• Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis

• Use doubly linked list and hash map.

1. The closer we get to the head of linked list, the more recently used. The end represent the least recently used node.
2. Every time we get the node, if the node exists, we set it to the head.
3. When we put the node, if the node exists, we update the node. if the cache size exceeds the capacity, remove the end node and update the hashmap.

160. Intersection of Two Linked Lists

Description

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

Analysis

• Create ptrA of headA and ptrB of headB
• When ptrA reaches the end the list, point to headB; when ptrB reaches the end the list, point to headA. Finally we can get the intersection.

203. Remove Linked List Elements

Description

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

Analysis

• Create dummy head and iterate through.

234. Palindrome Linked List

Description

• Given a singly linked list, determine if it is a palindrome.

Analysis

• Find the middle node and reverse the right half of the list.
• Then check if every node of two lists have the same value.

328. Odd Even Linked List

Description

• Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
• You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Analysis

• Iterate through the list to generate odd list and even list.

430. Flatten a Multilevel Doubly Linked List

Description

• You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
• Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Analysis

1. Start form the head , move one step each time to the next node
2. When meet with a node with child, say node p, follow its child chain to the end and connect the tail node with p.next, by doing this we merged the child chain back to the main thread
3. Return to p and proceed until find next node with child.
4. Repeat until reach null

708. Insert into a Cyclic Sorted List

Description

• Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.
• If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.
• If the list is empty (i.e., given node is null), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.

Analysis

• Consider three cases: 1. climbing, 2. tipping point, 3. all the same