# Linked List

## Singly Linked List

### Find Operation

It takes us `O(N)` time on average to `visit an element by index`, where N is the length of the linked list.

### Add Operation

#### Add a Node after a Given Node

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

Initialize a new node `cur` with the given value;

Link the "next" field of `cur` to prev's next node `next`;

Link the "next" field in `prev` to `cur`.

**O(1) time, space complexity**

[@LeetCode](https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1288/)![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F53042344d01d6c4246989a61f9cb46e856aec5c7.png?generation=1588144784156577\&alt=media)

#### Add a Node at the Beginning

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

#### Delete Operation

## Doubly Linked List

### Doubly Linked List Node Structure

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

## Linked List Basic Operations and Classic Problems

_**Based on Java, Singly Linked List**_

### ListNode Class

```java
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) { val = x; }
}
```

### Reverse a Linked List

Ref: [https://leetcode.com/articles/reverse-linked-list/](https://leetcode.com/articles/reverse-linked-list/)

**iterative**

```java
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
```

```java
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
```

**recursive**

```java
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}
```

```java
    ListNode newHead;
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        return reverseUtil(head, null);
    }
    ListNode reverseUtil(ListNode curr, ListNode prev) { 

        /* If last node mark it head*/
        if (curr.next == null) { 
            newHead = curr; 

            /* Update next to prev node */
            curr.next = prev; 

            return newHead; 
        } 

        /* Save curr->next node for recursive call */
        ListNode next = curr.next; 

        /* and update next ..*/
        curr.next = prev; 

        reverseUtil(next, curr); 
        return newHead; 
    }
```

### Find the Middle Point

If there are two middle nodes, return the second middle node.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
```

If there are two middle nodes, return the first middle node.

```java
public ListNode findMiddle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
```

### Find the Nth Element

```java
ListNode fast = head;
for (int i = 0; i < n - 1; i++) {
    fast = fast.next;
    if (fast == null) {
        return null;
    }
}
```

### Dummy Node

```java
ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode current = dummy;
...
while (current != null) {
    ...
    current.next = blahblahblah;
    ...
    current = current.next;
}
...
return dummy.next;
```

### Merge Two Sorted Lists

Iterative

```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode lastNode = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            lastNode.next = l1;
            l1 = l1.next;
        } else {
            lastNode.next = l2;
            l2 = l2.next;
        }
        lastNode = lastNode.next;
    }

    if (l1 != null) {
        lastNode.next = l1;
    } else {
        lastNode.next = l2;
    }

    return dummy.next;
}
```

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                p.next = l2;
                break;
            }
            if (l2 == null) {
                p.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        return dummy.next;
    }
}
```

Recursive

```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}
```

### Remove Linked List Elements

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

Iterative

```java
public ListNode removeElements(ListNode head, int val) {
   ListNode dummy = new ListNode(0);
   dummy.next = head;
   ListNode curr = head;
   ListNode prev = dummy;
   while (curr != null) {
      if (curr.val == val) {
           prev.next = curr.next; 
      } else {
           prev = prev.next;
      }  
      curr = curr.next;
   }
   return dummy.next;
}
```

Recursive

```java
public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
}
```

### Linked List Has Cycle

```java
public Boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode fast, slow;
    fast = head.next;
    slow = head;
    while (fast != slow) {
        if(fast==null || fast.next==null)
            return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
}
```

## Two Pointer Technique in Linked List 链表中的两个指针

For Linked List, we can use two-pointer technique:

> Two pointers are `moved at different speed`: one is faster while another one might be slower.

The scenario, which is also called `slow-pointer and fast-pointer technique`, is really useful.

Detect Cycles in Linked List

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

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

The proper speed for the two pointers?

Slow pointer - One step at a time

Fast pointer - Two steps at a time

#### 链表中快慢指针的Template

```java
// 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) {
    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**

**1. Always examine if the node is null before you call the next field.**&#x20;

**总是检查节点是否为null，否则node.next会导致null-pointer错误**

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.

## LinkedList vs ArrayList

### Hierarchy Diagram in Collection

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F0d67a04b04f621dbe6b7decee38186bcb4884fcc.png?generation=1588144784644692\&alt=media)

### Performance Comparison of ArrayList vs LinkedList

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2Fce6841a19183950f81e6171b1272685abaefa9ba.png?generation=1588144784319481\&alt=media)

**Reverse List in Java**

[https://www.techiedelight.com/reverse-arraylist-java/](https://www.techiedelight.com/reverse-arraylist-java/)

[https://www.geeksforgeeks.org/collections-reverse-java-examples/](https://www.geeksforgeeks.org/collections-reverse-java-examples/)

## [Data Structure Time Complexity Comparison](https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1230/)

Here we provide a comparison of`time complexity`between the linked list and other data structures including[array](https://leetcode.com/explore/learn/card/array-and-string/), queue and stack:

![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/29/screen-shot-2018-04-28-at-174531.png)

After this comparison, it is not difficult to come up with our conclusion:

> If you need to add or delete a node frequently, a linked list could be a good choice.
>
> If you need to access an element by index often, an array might be a better choice than a linked list.
