206.Reverse Linked List

Reverse a singly linked list.

簡單題目不簡單，數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)兆旬，在不生成新鏈表的情況下原地生成一個反轉(zhuǎn)鏈表。

var reverseList = (head) => {
    let tail = head;
    if (!head || !head.next) {
        return head;
    }
    while (tail.next) {
        let tmp = tail.next.next;
        tail.next.next = head;
        head = tail.next;
        tail.next = tmp;
    }
    return head;
};

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

上一題的擴(kuò)展桅狠，只反轉(zhuǎn)一部分鏈表济竹，可以繼續(xù)沿用上題的部分思想，通過一個depth來確認(rèn)鏈表反傳到了哪一層來跳出循環(huán)碴开。

var reverseBetween = function (head, m, n) {
    let curr = head;
    let depth = 0;
    let lastCurr;
    for (let i = 0; i < m - 1; i++) {
        lastCurr = curr;
        curr = curr.next;
    }
    let tail = curr;
    while (depth < n - m) {
        let tmp = tail.next.next;
        tail.next.next = curr;
        curr = tail.next;
        tail.next = tmp;
        depth++;
    }
    lastCurr ? (lastCurr.next = curr) : head = curr;
    return head;
};

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.


k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

將鏈表分成長度為k的數(shù)段，反轉(zhuǎn)每一段博秫，只允許使用常量級別的額外空間潦牛。

var reverseKGroup = function (head, k) {
    if (k === 1) {
        return head;
    }
    let curr = head;
    let headTail,tailHead,rowHead;
    let count = 0;
    while (curr) {
        if (!rowHead) {
            rowHead = curr;
            curr = curr.next;
        } else if ((count + 1) % k === 0) {
            tailHead = curr.next;
            curr.next = null;
            let [kHead, kTail] = reverseinK(rowHead);
            if (headTail) {
                headTail.next = kHead;
                kTail.next = tailHead;
                headTail = kTail;
            } else {
                head = kHead;
                headTail = kTail;
                headTail.next = tailHead;
            }
            rowHead = null;
            curr = tailHead;
        } else {
            curr = curr.next;
        }
        count++;
    }
    return head;
};

var reverseinK = function (head) {
    let tail = head;
    while (tail.next) {
        let tmp = tail.next.next;
        tail.next.next = head;
        head = tail.next;
        tail.next = tmp;
    }
    return [head, tail]
}