单链表反转 —— 变形

发表于

算法：单链表反转

题目

1
2
3
4
5
6
这其实是一道变形的链表反转题，大致描述如下

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

解析

这道题的难点在于，是从链表的尾部开始组起的，而不是从链表的头部，如果是头部的话，那我们还是比较容易做的，因为你可以遍历链表，每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起；

思路1：整体反转，然后从头开始截取 K个节点 ，被后续截图的K个节点 的尾部连接；最后长度不足K的节点再局部反转 作为 队头

思路2：整体反转，

​

Java解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Node {
    int val;
    Node next;
    public Node(int d) { this.val = d; }
}
class Solution {
    public Node reverse(Node node) {
        Node pre = node;
        Node cur = node.next;
        node.next = null;
        Node tmp;
        while(cur!=null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    public Node reverseByK(Node node, int k) {
        Node tmp = node;
        for (int i=1; i<k && tmp != null; i++) {
            tmp = tmp.next;
        }
        if (tmp == null) {
            return node;
        }
        Node childList = tmp.next;
        tmp.next = null;
        Node retNode = reverse(node);
        Node newChildNode = reverseByK(childList, k);
        node.next = newChildNode;
        
        return retNode;
    }
    public static void main(String[] args) {
        Node link = null;
        Node tmp = link;
        for(int i=1; i<9; ++i) {
            if(null == tmp) {
            	tmp = new Node(i);
            	link = tmp;
            } else {
            	tmp.next = new Node(i);
            	tmp = tmp.next;
            }
        }
        Solution solution = new Solution();
        link = solution.reverse(solution.reverseByK(solution.reverse(link), 3));
        while(link!=null) {
            System.out.print(link.val + " ");
            link = link.next;
        }
    }
}

Python解法

​