1. The basics of linked lists

What is a linked list? A linked list is a discontinuous, non-sequential storage structure on a physical storage cell. The logical order of data elements is realized by linking the order of Pointers in the list. A linked list consists of nodes, each of which consists of two parts:

  • Stored data domains
  • A pointer field that stores the address of the next node

A graph represents a linked list

Linked list code implementation

class ListNode { val: number; next: ListNode | null; constructor(val: number, next: ListNode | null = null) { this.val = val; this.next = next; }}Copy the code

2. Use of linked lists

2.1 Inserting nodes

2.1.1 Sequential inserts — Add to the end of the list

const head = new ListNode(0)
​
// Insert the node
head.next = new ListNode(1)
head.next.next = new ListNode(2)
head.next.next.next = new ListNode(3)
console.log(head)
/** ListNode { val: 0, next: ListNode { val: 1, next: ListNode { val: 2, next: null } } } */
Copy the code

Same operation, a little more elegant, encapsulate

const head = new ListNode(0.new ListNode(1))
​
function insertToTail(list: ListNode | null, value: number) {
  if(! list)return new ListNode(value)
  let p = list
  while (p.next) {
    p = p.next
  }
  p.next = new ListNode(value)
}
​
// call it
insertToTail(head, 2)
Copy the code

Because of the pointer reference, the p that you end up with is actually the last bit of the list, P.ext = new ListNode(value) = new ListNode(value) = next = new ListNode(value)

2.1.2 Midway insertion

Once you understand the sequence above, it’s easy to insert halfway through

// Insert a node after the target node in the linked list
​
const head = new ListNode(0.new ListNode(1))
/** ** ** /** *@target Target position *@node The node */ inserted after the target position
function insertToTarget(list: ListNode, target: number, node: ListNode) {
  let p = list
  while (p) {
    if (p.val === target) {
      node.next = p.next // Set next of the node to be inserted to next of the target node
      p.next = node // Set next of the target node to the node to be inserted
      return
    }
    p = p.next
  }
}
​
const node = new ListNode(3)
​
insertToTarget(head, 0, node)
console.log(head) // 0, 3, 1
​
Copy the code

Other complex operations are basically based on this, and it’s not that hard to understand.

2.2 Deleting a Node

After playing around with insert nodes, it’s easy to delete nodes and delete head nodes

// There is no (note that the value reference is changed pit)
function removeHeadNode (head: ListNode | null) {
  if(! head)return null
  return head.next
}
​
// New ListNode is not a new ListNode. It is simpler and more intuitive to use array representation
let head = [1.2.3]
​
head = removeHeadNode(head)
console.log(head) / / [2, 3]
Copy the code

Deleting a Node

function removeTargetHandle(head: ListNode | null, target: number) {
  if(! head || head.val === target)return null // If the header is the target node, it is processed directly
  let p = head
  while(p && p.next) {
    if (p.next.val === target) { // Find next val every time
      p.next = p.next.next // Overwrite the next node
      return head
    }
    p = p.next
  }
  return head
}
Copy the code

Let’s go to Leetcode and delete duplicate elements from the sorted list

function deleteDuplicates(head: ListNode | null) :ListNode | null {
  if(! head || ! head.next)return head
  let p = head
  while(p && p.next) {
    if (p.val === p.next.val) {
      // Keep the current, remove next, the pointer is still the element in head
      // Note the pointer problem mentioned above, p = p.ext.next will not change to head
      p.next = p.next.next 
    } else {
      p = p.next
    }
  }
  return head
};
Copy the code

Delete duplicate element 2 from the linked list

function deleteDuplicates(head: ListNode | null) :ListNode | null {
  if(! head || ! head.next)return head
  let ret = new ListNode(-1, head) // Create an empty header pointer
  let slow = ret
  let fast = head
  while (fast && fast.next) {
    if(fast.next.val ! == slow.next.val) {// If the next elements of the fast and slow Pointers are not equal, each jumps one bit
      fast = fast.next
      slow = slow.next
    } else {
      while(fast && fast.next && fast.next.val === low.next.val) { // Next equals next
        fast = fast.next
      }
      // Skip the current known repeating elements such as fast to 1, 2, 3, 3
      // Slow points to 2, then slow next points to fast. Next skips the repeated 3
      slow.next = fast.next 
      fast = fast.next
    }
  }
  return ret.next
};
Copy the code

If you don’t understand, you can draw a picture to help you understand

2.3 find

Circular linked list

// Do you have any questions
function hasCycle(head: ListNode | null) :boolean {
	if(! head)return false
  let slow = head
  let fast = head.next
  while(slow ! == fast && slow && fast && slow.next && fast.next) { slow = slow.next fast = fast.next.next }// This is probably because slow and fast are the same
  if(slow ! == fast)return false // It is also possible for the list loop to end
  return true
};
Copy the code

Circular linked list II

function detectCycle(head: ListNode | null) :ListNode | null {
    if(! head)return null
    let slow = head
    let fast = head.next
    while(slow ! == fast && slow && fast && slow.next && fast.next) { slow = slow.next fast = fast.next.next }// The list may not have a ring, or it may have a ring
    if(slow ! == fast)return null // The list has no loops
    // Lists have rings, that's the point
    // head = [3,2,0,-4], pos = 1 (value 2)
  	// The fast pointer always moves one more step at a time than the slow pointer. The fast and slow Pointers intersect at 0
    // The distance from the intersection to the ring is the same as the distance from the header to the ring
    slow = head // A pointer moves to the head node
    fast = fast.next // A pointer moves to next
    while(slow ! == fast) { slow = slow.next fast = fast.next }return slow // Return the point of encounter
};
Copy the code

Step by step, starting with the linked list!