茄子算法每日N题之LeetCode25K个一组翻转链表

javascript/jquery

浏览数:119

2020-5-26

LeetCode 25.K个一组翻转链表

大家好,我是灵魂画师–茄子。技术水平一般,喜欢画画。

开始今天的正题。

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

题解:
1.递归解法

优先看图解

  1. 设立俩个指针分别指向null和head
  2. 设立一个p,用p每次传入的head是否够一组,不够一组直接返回。
  3. 设立一个i = 0,循环k次 ,k次后跳出循环,让head.next = 函数递归调用。
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
let reverseKGroup = function(head, k) {
    let pre = null;
    let cur = head;
    let p = head;
    let i = 0;
    let j = 0;
    console.log(head)
    while( i < k){
        if(p == null){
            return head;
        }
        i++;
        p = p.next;
    }
    while(j < k){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        j++;
    }
    console.log(head)
    head.next = reverseKGroup(cur, k);
    return pre;
};

2.利用栈解法

思路:

  1. 第一次压入K个节点。
  2. 如果不够一组,则直接返回。
  3. 第一次出栈K个长度,让最后一个的next指向下一组的开头
  4. 然后开始下一组的入栈,重复步骤1。

结合图解,结合代码,梳理一下思路。我认为栈理解起来比递归还要简单一些。

let reverseKGroup = function(head, k) {
    let stack = [];
    let preHead = new ListNode(0);
    let pre = preHead;
    // 循环链接后续反转链表
    while(true){
        let count = 0;
        let tmp = head;
        while(tmp && count < k){
            stack.push(tmp);
            tmp = tmp.next;
            count++;
        }
        // 不够k个,直接链接剩下链表返回
        if(count != k){
            pre.next = head;
            break;
        }
        // 出栈即是反转
        while(stack.length > 0){
            pre.next = stack.pop();
            pre = pre.next;
        }
        pre.next = tmp;
        head = tmp;
    }
    return preHead.next;
};

作者:灵魂画师_茄子