This is the seventh 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

DAY8

1. Reverse the list

Given the head node of the single linked list, please reverse the list and return the inverted list.

Input: head = [1,2,3,4,5]Copy the code
  • General solution: the list of problems are usually recursion to solve, this problem can be usedrecursiveandDouble pointerIn fact, the idea is the same look at the picture 👇🏻

Method 1: recursion

It’s a little hard to understand recursively, but it’s the same thing as a double pointer, where you point the next pointer backwards

function reverseList(head: ListNode | null) :ListNode | null {
    Return the current head if the current list and the next list do not exist
    if (head == null || head.next == null) {
        return head;
    }
    / / recursion
    const newHead = reverseList(head.next);
    // Make the list pointer point backward
    head.next.next = head;
    head.next = null;

    return newHead;
};
Copy the code

Method 2: Double pointer

Double pointer code is a little clearer.

  1. Define two Pointers and registers
  2. Let the first header point to null to represent the last
  3. Move the pointer 2 at a time
  4. TMP: Register saves the next linked list
  5. 2 lists switch positions
function reverseList(head: ListNode | null) :ListNode | null {
    if(! head || ! head.next)return head;

    // Pointer pre
    let pre = null
    // Define registers
    let tmp = null
    // pointer cur
    let cur = head

    // Move the pointer
    while(cur) {
        tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
};
Copy the code

2. Delete duplicate elements from the sorted list

Example 1:

There is a linked list in ascending order. Give you the head node of the list. Please delete all duplicate elements so that each element appears only once. Returns a linked list of results, also in ascending order.Copy the code

Input: head = [1,1,2]Copy the code

Example 2:

Input: head = [1,1,2,3,3] output: [1,2,3]Copy the code

Method 1: Make a loop

Note 📢 : the list is sorted!

  • We just need to go through it once, keep comparing it to the next element, and if it’s equal, skip it
function deleteDuplicates(head: ListNode | null) :ListNode | null {
    if(! head)return head

    let item = head
    
    // Since the list is in ascending order, we can continuously compare the current list with the next list, and if there is any duplication, we will skip it
    while (item.next) {
        if (item.val === item.next.val) {
            // Repeat, skip
            item.next = item.next.next;
        } else {
            item = item.next
        }
    }

    return head
};
Copy the code

The popular science article

Pictures and text, all from the Internet

  • The list

Data is stored linearly sequentially, instead storing Pointers to the next node in each node. Because they do not have to be stored in order, the insertion and deletion operations can reach O(1) complexity. This article covers both unidirectional and bidirectional lists, with bidirectional lists showing some key code implementations.

  1. Singly linked list

A unidirectional linked list (singly linked list) is a type of linked list. It consists of nodes, each node contains a pointer to the next node. The following figure is a singly linked list with an empty header.

  1. Two-way linked list

A bidirectional linked list (double linked list) is a type of linked list. Like a single linked list, a double linked list is made up of nodes. Each data node has two Pointers, one to a direct successor and the other to a direct precursor. Therefore, starting from any node in the bidirectional linked list, it is easy to access its predecessors and successors. In general, we construct two-way circular lists.