This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

The title of this article is all from LeetCode

Use the Typescript

This article is part of the column 3 Week Conquer Data structure-Leetcode

All the code and problem-solving steps in this article will be placed in the GitHub repository

DAY7

1. Ring 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 continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list. Returns true if there is a loop in the list. Otherwise, return false.Copy the code

Enter: head = [3,2,0,-4], pos = 1

Output: true,

Explanation: There is a loop in a linked list with a second node at the end.


Enter: head = [1], pos = -1

Output: false

Explanation: There are no rings in a linked list.

The construction method of singly linked list: 👇🏻

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

Method 1: Hash table query

  1. Create a hash table to store the processed values
  2. Traversing a linked list; If the list contains the current value, there is a change
function hasCycle(head: ListNode | null) :boolean {
    // Create a table record
    const MAP = []

    while(head) {
        // There is a ring
        if(MAP.includes(head)){
            return true
        }
        // Count the judged items into the hash table
        MAP.push(head)
        // Determine the next link
        head = head.next
    }

    / / no ring
    return false
};
Copy the code

Method 1-1: Hash table extension method: Linked list recording method, also known as dirty list method

  1. Add a flag identifier to the found link

  2. An identifier encountered indicates a ring

    • Disadvantages: Changes to existing data structures
    • Advantages: No need for a separate booth for memory
function hasCycle(head: any): boolean {
    while (head) {
        if(head.flag) {
            return true
        }
        head.flag = true;
        head = head.next;
    }

    return false
};
Copy the code

Method 2: fast pointer

The principle of the fast pointer is roughly the same as the double pointer problem we did before:

  • One is to shorten the path with two Pointers, and one is to reduce the memory footprint with two Pointers (compare hash table solutions).
  • The principle of the fast and slow pointer is very simple is to go through the list once, the fast pointer is one step faster than the slow pointer, the pointer overlap means there is a loop
function hasCycle(head: ListNode | null) :boolean {
    if(! head)return false

    // Initialize the fast pointer and the slow pointer
    let slow_p = head
    let fast_p = head

    while(fast_p.next ! = =null&& fast_p.next.next ! = =null) {
        // The fast pointer is one step faster than the slow pointer
        slow_p = slow_p.next
        fast_p = fast_p.next.next
        // If the fast pointer catches up with the slow pointer, the loop is proved
        if (slow_p === fast_p) return true
    }

    return false
};
Copy the code

Method 3: JS language features

The json. stringify method automatically checks whether the passed object is a ring. If json. stringify executes successfully, it must not be a ring

function hasCycle(head: ListNode | null) :boolean {
    try {
        JSON.stringify(head)
        return false
    } catch {
        return true}};Copy the code

2. Merge two ordered lists

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists.

Input: l1 = 4-trichlorobenzene [1], l2 = [1 4] output:,1,2,3,4,4 [1] example 2: input: l1 = [], l2 = [] output: [] example 3: input: l1 = [], l2 = [0] output: [0] tip: The number of nodes in the two linked lists ranges from [0, 50] -100 <= node. val <= 100 l1 and L2 are arranged in non-decreasing orderCopy the code

Method 1: recursion

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null) :ListNode | null {
    
    // One of them is empty
    if(! l1 || ! l2) {return l1 || l2
    } 

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        returnl2; }};Copy the code

Approach 2: Iterate

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null) :ListNode | null {
    Nwe = nWE = nWE = nWE = nWE
    const newList = new ListNode(0);
    let cur = newList;

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

    // At most, only one of the two lists has not been merged
    cur.next = l1 ? l1 : l2;
    return newList.next;
};
Copy the code

3. Remove a linked list element

Method 1: recursion

function removeElements(head: ListNode | null, val: number) :ListNode | null {
    if (head === null) return head

    head.next = removeElements(head.next, val); 
    // The current list is skipped if the condition is met
    return head.val === val ? head.next : head;

};
Copy the code

Approach 2: Iterate

function removeElements(head: ListNode | null, val: number) :ListNode | null {
   const preHead = new ListNode(0);
    preHead.next = head;

    let cur = preHead;

    while(cur.next ! = =null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        } else{ cur = cur.next; }}return preHead.next;
};
Copy the code

conclusion

Linked list data structures, mostly using recursive processing