1. Delete the last but one node of the linked list

Given a linked list, delete the last a node from the list and return the head of the list.

1.1 Dual-pointer solution

If we want to delete the last a node from the last a node, we need to know which node is next to the last A node, and then point next to next on the last A node. To delete the penultimate node a of the linked list, we can set two Pointers P and q. P goes to a node first, and then P and Q go at the same time. In this way, when P reaches the end, Q’s position will be the previous node of the penultimate node A.

The code implementation is as follows:

var removeNthFromEnd = function(head, n) {
    let newHead = new ListNode(0, head);
    let p = newHead;
    let q = newHead;
    while(n > 0) {
        p = p.next;
        n -= 1;
    }
    while(p.next ! = =null) {
        q = q.next;
        p = p.next;
    }
    q.next = q.next.next;
    return newHead.next;
};
Copy the code

2. Rotate the list

Give you the head of a linked list, rotate the list, and move each node k positions to the right.

2.1 Solution ideas

First of all, we need to know that when k is equal to the length of the list (n), there is no movement, so when k is greater than the length of the list, we need to figure out the actual number of moves, which should be equal to k%n. Next, move the pointer from the start to n-k%n, then point the current node to null, and then point the last node to the start node.

The code implementation is as follows:

var rotateRight = function(head, k) {
    if(! head)return null;
    let p = head;
    let i = 1;
    while(p.next) {
        i += 1;
        p = p.next;
    }
    p.next = head;
    k = k % i;
    k = i - k;

    while(k ! = =0) {
        p = p.next;
        k -= 1;
    }
    const temp = p.next;
    p.next = null;
    return temp || p;
};
Copy the code

3. Delete duplicate elements from the sorted list

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once.

Returns a linked list of results, also in ascending order.

3.1 Solution idea

This list is already sorted first okay, so, repetition is continuous, so in the traversal, the value of the current node and compare it to the next node, if the same, will be the next point to the next node next, at the same time the current node into the next node, not the same, will be the current node into the next node.

The code implementation is as follows:

var deleteDuplicates = function(head) {
    let p = head;
    while(p) {
        if (p.next && p.val === p.next.val) {
            p.next = p.next.next;
        } else{ p = p.next; }}return head;
};
Copy the code

4. Reverse the linked list

Given the head node of a single linked list, reverse the list and return the reversed list.

Click here to solve LeetCode

4.1 Solution idea

Reversing the linked list is actually to point the next of the current node to its previous node, so we can define two variables, one for the previous node and one for the current node.

The code implementation is as follows:

var reverseList = function(head) {
    if(! head || ! head.next)return head;
    let p = head;
    let pre = null;
    while(p.next) {
        let temp = p;
        p = p.next;
        temp.next = pre;
        pre = temp;
    }
    p.next = pre;
    return p;
};
Copy the code

5. Flip linked lists in groups of K

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order. Click here to solve LeetCode

5.1 Solution Ideas

Personally, I understand that this problem and reverse list can be used to solve the same idea, but this is just a group of reverse list. It should be noted that after the list inversion of a group is complete, the head node becomes the tail node, the tail node becomes the head node, and the next of the tail node should point to the head node of the next group.

The code implementation is as follows

var reverseKGroup = function(head, k) {
    if (k === 0 || k === 1) {
        return head;
    }
    let i = 1;
    let newHead;
    let curGroupLastNode;
    let curGroupHead = head;
    let p = head;
    while(true) {
        if (i % k === 0) {
            if (curGroupLastNode) {
                curGroupLastNode.next = p;
            }
            curGroupLastNode = curGroupHead;
            curGroupHead = p.next;
            p.next = null;
            let q = reverseList(curGroupLastNode);
            
            if(! newHead) { newHead = q; } curGroupLastNode.next = curGroupHead; p = curGroupHead; }else {
            p = p.next; 
        }
        if(! p) {return newHead;
        }
        
        i += 1;
    }

    function reverseList(head) {
        if(! head || ! head.next)return head;
        let p = head;
        let pre = null;
        while(p.next) {
            let temp = p;
            p = p.next;
            temp.next = pre;
            pre = temp;
        }
        p.next = pre;
        return p;
    };
    return head;
};
Copy the code

6. Return the KTH penultimate node

Implement an algorithm to find the penultimate KTH node in a one-way linked list. Returns the value of this object.

Click here to solve LeetCode

6.1 Solving the problem

This is the same idea as deleting the last a node from the list, except that it returns the value of Val for Next.

The code implementation is as follows:

var kthToLast = function(head, k) {
    let newHead = new ListNode(0, head);
    let p = newHead;
    let q = newHead;
    while(k > 0) {
        p = p.next;
        k -= 1;
    }
    while(p.next ! = =null) {
        q = q.next;
        p = p.next;
    }
    return q.next.val;
};
Copy the code