Leetcode – Linked list (JS implementation)

237. Delete a node from a linked list

Input: head = [4,5,1,9], node = 5 Output: [4,1,9]Copy the code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};
Copy the code

18. Remove nodes from the list

Input: head = [4,5,1,9], val = 5 Output: [4,1,9]Copy the code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var deleteNode = function(head, val) {
    let dummpy = new ListNode();
    dummpy.next = head;
    let cur = dummpy;
    while(cur.next){
        if(cur.next.val === val) {
            cur.next = cur.next.next;
            break;
        }
        cur = cur.next;
    }
    return dummpy.next;
};
Copy the code

160. Intersecting linked lists

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.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}* /
var getIntersectionNode = function(headA, headB) {
    let curA = headA;
    let curB = headB;
    while(curA ! == curB) { curA = curA ===null ? headB : curA.next;
        curB = curB === null ? headA : curB.next;
    }
    return curA;
};
Copy the code

Delete the NTH node from the list

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

Input: head = [1,2,3,4,5], n = 2Copy the code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
    / * * *@param {ListNode} head
    * @param {number} n
    * @return {ListNode}* /
    var removeNthFromEnd = function(head, n) {
        let dummy = new ListNode();
        dummy.next = head;
        let slow = dummy;
        let fast = dummy;
        while(n ! = =0) {
            fast = fast.next;
            n--;
        }
        while(fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    };
Copy the code

21. Merge 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

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
    const dummpy = new ListNode();
    let cur = dummpy;
    while(l1 && l2) {
        if(l1.val > l2.val) {
            cur.next = l2;
            l2 = l2.next;
        } else {
            cur.next = l1;
            l1 = l1.next;
        }
        cur = cur.next;
    }
    cur.next = l1 ? l1 : l2;
    return dummpy.next;
};
Copy the code

The middle node of a linked list

Given a non-empty singly linked list with head, return the middle node of the list.

If there are two intermediate nodes, the second intermediate node is returned.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};
Copy the code

206. Reverse linked lists

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

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

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur){
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};
Copy the code

328. Odd-even linked lists

Given a singly linked list, rank all the odd and even nodes together. Note that the odd and even nodes here refer to the parity of node numbers, not the parity of node values.

Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULLCopy the code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var oddEvenList = function(head) {
    if(! head)return head;
    let odd = head;
    let even = head.next;
    let evenStart = even;
    while(even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenStart;
    return head;
};
Copy the code