A linked list is a data structure that consists of a sequence of nodes. Each node is composed of data and a reference/link to the next node in the sequence. A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations (unlike an array).

     node #1            node #2             node #3
┌───────┬───────┐   ┌───────┬───────┐   ┌───────┬───────┐
│ value │ next  ├──►│ value │ next  ├──►│ value │ next  ├──► null
└───────┴───────┘   └───────┴───────┘   └───────┴───────┘

Example ListNode class that has values of type int (Java)

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

Usage

ListNode node1 = new ListNode(4);
node1.next = new ListNode(2);

Result

node1
┌───┐   ┌───┐
│ 4 ├──►│ 2 ├──► null
└───┘   └───┘

1) Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the head of the linked list with the duplicates removed.

Example 1:

         ┌───┐   ┌───┐   ┌───┐   
Input :  │ 1 ├──►│ 1 ├──►│ 2 ├──► null
         └───┘   └───┘   └───┘   
         ┌───┐   ┌───┐
Output:  │ 1 ├──►│ 2 ├──► null
         └───┘   └───┘

Example 2:

         ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
Input:   │ 1 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 3 ├──► null
         └───┘   └───┘   └───┘   └───┘   └───┘
         ┌───┐   ┌───┐   ┌───┐   
Output:  │ 1 ├──►│ 2 ├──►│ 3 ├──► null
         └───┘   └───┘   └───┘

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

2) Reverse Linked List

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

Example 1:

         ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
Input:   │ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 │──►│ 5 │
         └───┘   └───┘   └───┘   └───┘   └───┘

         ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
Output:  │ 5 ├──►│ 4 ├──►│ 3 ├──►│ 2 │──►│ 1 │
         └───┘   └───┘   └───┘   └───┘   └───┘

Example 2:

         ┌───┐   ┌───┐
Input:   │ 1 ├──►│ 2 │
         └───┘   └───┘

         ┌───┐   ┌───┐
Output:  │ 2 ├──►│ 1 │
         └───┘   └───┘

Constraints:

  • The number of nodes in the list is the range [0, 5000].
  • 5000 <= Node.val <= 5000

3) Linked List Cycle

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

        ┌───┐   ┌───┐   ┌───┐   ┌───┐
Input:  │ 3 ├──►│ 2 ├──►│ 0 ├──►│-4 │
        └───┘   └───┘   └───┘   └─┬─┘
                  ▲               │
                  └───────────────┘
                  
Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

        ┌───┐   ┌───┐
Input:  │ 1 ├──►│ 2 │
        └───┘   └─┬─┘
          ▲       │
          └───────┘
          
Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

        ┌───┐
Input:  │ 1 ├──► null
        └───┘

Output: false

Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

4) Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the value of the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

There are no cycles anywhere in the entire linked structure. Note that the linked lists must retain their original structure after the function returns.

Example 1:

Input:
        ┌───┐   ┌───┐
        │ 4 ├──►│ 1 ├───┐
        └───┘   └───┘   ▼
                      ┌───┐   ┌───┐   ┌───┐
                      │ 8 ├──►│ 4 ├──►│ 5 ├──► null
                      └───┘   └───┘   └───┘
┌───┐   ┌───┐   ┌───┐   ▲
│ 5 ├──►│ 6 ├──►│ 1 ├───┘
└───┘   └───┘   └───┘

Output: 8

Explanation: The intersected node's value is 8.

- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node 
  in B) are different node references. In other words, they point to two different locations in memory, while the nodes with
  value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input:
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 9 ├──►│ 1 ├───┐
└───┘   └───┘   └───┘   ▼
                      ┌───┐   ┌───┐
                      │ 2 ├──►│ 4 ├──► null
                      └───┘   └───┘
                ┌───┐   ▲
                │ 3 ├───┘
                └───┘
                
Output: 2

Example 3:

Input:
┌───┐   ┌───┐   ┌───┐
│ 2 ├──►│ 6 ├──►│ 4 ├──► null
└───┘   └───┘   └───┘
        ┌───┐   ┌───┐
        │ 1 ├──►│ 5 ├──► null
        └───┘   └───┘

Output: null

Explanation: The two lists do not intersect, so return null.

Constraints:

  • The number of nodes of listA is greater than or equal to 1.
  • The number of nodes of listB is less than or equal to 3 * 10^4.
  • 1 <= Node.val <= 10^5

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?