Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL; DR

  • In JS, a list is a nested object,{val:1,next:{val:2,next:... }}
  • The Pointers in the list, which sounds abstract, are part of the list, are still nested objects, p is{val:1,next:{val:2,next:... }}
  • If I move the needle back, it’s actuallyp = p.nextThat is, p becomes{val:2,next:... }
  • The last node in the list,nextIt must be empty
  • When dealing with linked lists, for the sake of boundary problems, many times create an empty node to point to the list

Basics: How does JS stand for linked lists

JS, there is no such data type as linked lists, so use objects to express linked lists

// List node class
function ListNode(val) {
  this.val = val;
  this.next = null;
}
Copy the code

If a linked list is 1->2->4, the expression JS

{
  val:1.next: {val:2.next: {val:4.next:null}}}Copy the code

Basics: Iterate over a linked list

When you walk through a list, you usually walk through it with a pointer, and when the pointer moves back, it gets empty

function walkList(list) {
  // point to the first node first
  let p = list;
  while (p) {
    // Prints the value of the node corresponding to the current pointer
    console.log(p.val);
    // Move the pointer back
    p = p.next;
  }
  // if p is empty, we are done iterating
  console.log("I'm done.");
}
Copy the code

Add a node

If 1->2->4 wants to add a new node, add 1->2->3->4 next pointer to 4 2 next pointer to 3

// Create a new node
const newNode = new ListNode(3);
// Find the pointer to the node before the new node, i.e. the pointer to node 2
const p2 = list1.next;
// Find the pointer to the next node after the new node, i.e. the pointer to node 4
const p4 = p2.next;
// Next of the new node points to a pointer to the next node
newNode.next = p4;
// The previous pointer to the new node points to the new node
p2.next = newNode;
Copy the code

Deleting a node

1->2->4, if you want to delete a node, 1->4 points directly to 4

// Avoid deleting the last node
p1.next = p1.next.next ? p1.next.next :null;
Copy the code

Basics: Create a new linked list

Create a new linked list 1->2, which, as a boundary, will normally have a null header


/ / the new node
const n1 = new ListNode(1)
const n2 = new ListNode(2)
// As a boundary, it is customary to set the value of the first node to null
// In order to know the reference to the first node later, we must have a head pointer
let head = new ListNode();
// The pointer to the new list, where p is the pointer, moves
let p = head
p.next = n1
// The pointer moves
p = p.next
// List lengthening
p.next = n2
// The pointer moves
p = p.next

const newList = head.next

Copy the code

Exercise: Merge linked lists

  • The new list
  • List 1 and list 2 are traversed by one pointer each
  • Compare the sizes and put them in a new list

Imagine that each node is a button, and the pointer to the new list acts like a string, threading the button.

function ListNode(val, next) {
  this.val = val;
  this.next = null;
}
function mergeTwoLists(l1, l2) {
  let p1 = l1;
  let p2 = l2;
  // The first empty node is used to avoid boundary problems, and the reference must be saved
  let head = new ListNode();
  head.next = list;
  // The pointer to the new list
  let p = head;
  while (p1 && p2) {
    if (p1.val <= p2.val) {
      // List lengthening
      p.next = new ListNode(p1.val);
      // The pointer moves
      p1 = p1.next;
      p = p.next;
    } else {
      // List lengthening
      p.next = new ListNode(p2.val);
      // The pointer movesp2 = p2.next; p = p.next; }}// List 1 and list 2 must have been traversed
  p.next = p1 ? p1 : p2;
  // Header references are used at this point, but not the first empty node
  return head.next;
}
Copy the code

Check out the official video

Exercise: Delete duplicate nodes

  • Repeating nodes must be adjacent because they are ordered
  • For the boundary problem, add an extra header
  • Iterate over, the pointer points to the current node, judge and the next node is the same, delete the next node
  • If not, move the needle forward
function ListNode(val, next) {
  this.val = val;
  this.next = null;
}
var deleteDuplicates = function (head) {
  let head = new ListNode();
  head.next = list;
  let p = head;
  while (p && p.next) {
    // If the adjacent nodes are equal, the pointer will move until the nodes are not equal
    while (p && p.next && p.val === p.next.val) {
      // Delete the node directly; If there's no lower node, it's the tail node, and it's just null
      p.next = p.next.next ? p.next.next : null;
    }
    // The pointer moves
    p = p.next;
  }
  return head.next;
};
Copy the code

Although it looks like a two-layer loop, in fact, each node is only traversed once, so the time complexity is O(n), and the space complexity is O(1).

Official video explanation

Exercise: Delete duplicate node upgrades

Here, the duplicate nodes themselves are also deleted.

Itself also deleted, very important! Because the linked list is deleted, it is necessary to know the front node! So, as we traverse, the pointer points to the current node, but compares the next node to the next node

  • Boundary problem, plus empty front node
  • When the value is the same, delete the two nodes, and then see if the next node is equal to the value of the previous one. If so, continue to delete until the value is not equal, which will delete all adjacent nodes
  • When the value is different, the pointer moves
function ListNode(val, next) {
  this.val = val;
  this.next = null;
}
var deleteDuplicates = function (list) {
  let head = new ListNode();
  head.next = list;
  let p = head;
  // Because the two nodes after the pointer are compared, we must determine the case in
  while (p && p.next && p.next.next) {
    /* All nodes with the same value are deleted */
    // Start with two nodes with the same value. Delete both nodes
    if (p.next.val === p.next.next.val) {
      let cur = p.next.val;
      p.next = p.next.next.next ? p.next.next.next : null;
      // Then check whether the next node is the same as the deleted node. If so, delete the node until the value of the next node is different from that of the deleted node
      while (p.next && p.next.val === cur) {
        p.next = p.next.next ? p.next.next : null;
      }
    /* Delete all objects with the same value. End */
    } else{ p = p.next; }}return head.next;
};
Copy the code

Time is still O(n), time is O(1).

The official resolution

reference

  • The front-end algorithm and data structure of xiuyan