Updates continue at……

Linear lists are divided into sequential representation and chained representation. This article focuses on chained representation, which is the structure of a linked list.

The basic concept

Linked lists are divided into linear linked lists, circular linked lists, and bidirectional linked lists

  • The chained storage structure of a linear table is characterized by an arbitrary set of storage cells that store the data elements of a linear table (this set of storage cells can be continuous or discontinuous)

  • A node containing two fields, data field and pointer field

  • N nodes are linked to form a linked list, which is a linear list

Various operating

Reverse a linked list

Solution one: recursion

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    // Use the following node as the header
    if (head == null || head.next == null) {
        return head;
    }
    / / recursion
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};
Copy the code

Solution two: iteration + double pointer

/ / iteration! Double pointer
var reverseList = function(head) {
    let prev = null;/ / before the pointer
    let curr = head;// Current pointer
    while (curr) {
        const next = curr.next;// The next pointer to the current pointer is saved
        curr.next = prev;
        prev = curr;/ / to go forward
        curr = next;/ / to go forward
    }
    return prev;
};
Copy the code

Circular linked list

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list.

// Label each node
const hasCycle = function(head) {
  while (head) {
    if (head.tag) {
      return true;
    }
    head.tag = true;
    head = head.next;
  }
  return false;
};
Copy the code

The KTH last node in a linked list

Given a linked list: 1->2->3->4->5, and k = 2. Return to list 4->5.Copy the code

Solution: Fast or slow pointer

var getKthFromEnd = function(head, k) {
    //p is slow, q is fast, q takes k steps first, then p and q together
    let p=head,q=head,i=0
    while(q){
        if(i>=k){
            p=p.next
        }
        q=q.next
        i++
    }
    return i>=k ? p : null
};
Copy the code

Merges two ordered lists

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Input: l1 = [1,2,4], l2 = [1,3,4]Copy the code
Input: L1 = [], L2 = [0] output: [0]Copy the code

Solution: Set dummy + iteration

var mergeTwoLists = function(l1, l2) {
    const prehead=new ListNode(-1);// Set a dummy node with a value of -1 that can be used to return the entire list

    let prev = prehead;// Set a dynamic node for movement
    while(l1! =null&& l2! =null) {// Jump out of while when one or both ends
        if(l1.val<=l2.val){
            prev.next=l1;// When l1 is smaller, point to l1
            l1=l1.next// change l1 to L1.next iteration
        }else{
            prev.next=l2/ / in the same way
            l2=l2.next/ / in the same way
        }
        prev=prev.next// Prev image moves back one bit
    }
    // connect to the end of L1 or L2
    prev.next = l1 === null? l2:l1return prehead.next// return the list
};

Copy the code

Cross linked list

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Solution 1: hash table + traversal

// Use hash table to cross linked lists
var getIntersectionNode = function(headA, headB) {
    const visited = new Set(a);//Set only stores keys
    let temp = headA;
    while(temp! = =null){
        visited.add(temp)// This is headA
        temp=temp.next
    }
    temp = headB;
    while(temp! = =null) {if(visited.has(temp)){
            return temp
        }
        temp=temp.next/ / traverse headB
    }
    return null;// Return null if not found
};
Copy the code

Solution two: alternating + before and after

var getIntersectionNode = function(headA, headB) {
        if(headA===null || headB === null) {return null
        }// If either one is empty, there is no intersection
        let pA =headA,pB=headB
        while(pA! ==pB){// When the intersection is not found
            pA= pA===null ? headB : pA.next// If you can't find it, change the list
            pB= pB===null ? headA : pB.next/ / same as above
        }// There are always some people who will exchange first and some people who will exchange later
        // (unless the two lists are of the same length, in which case the first list can be found, no need to swap)
        // Because of this sequence, sooner or later, we will encounter the situation that we can walk the same distance to the intersection point
        return pA
};
Copy the code

Palindrome list

Give you a single linked list of the head node head, please determine whether the list is a palindrome list. If so, return true; Otherwise, return false.

Example 1:

Input: head = [1,2,2,1] output: true

Solution: Convert to array + double pointer

 // Palindromes are words that read the same way before and after
 // Store as an array and then use a double pointer
var isPalindrome = function(head) {
    let current=head
    const arr=[]// Create an array to hold the list values
    while(current){
        arr.push(current.val)
        current=current.next
    }
    let p,q;/ / double pointer
    for(let i=0; i<arr.length; i++){ p=arr[i] q=arr[arr.length-1-i]
        if(p! =q){// They are not symmetrical when they are different
            return false}}return true
};
Copy the code