《算法通关村第二关黄金挑战一一K个一组反转》

《算法通关村第二关黄金挑战一一K个一组反转》

描述

每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

解法

头插法

理解图：

穿针引线法

理解图

代码实现

package AlgorithmSecond;

import AlgorithmFirst.LinkedNode;

public class GroupReverse {
    /**
     * 头插法
     *
     * @param head
     * @param k
     * @return
     */
    public static LinkedNode HeadInsertMethod(LinkedNode head, int k) {
        LinkedNode dummyNode = new LinkedNode(0);
        dummyNode.setNext(head);
        LinkedNode cur = head;
        int len = 0; // 先计算出链表的长度
        while (cur != null) {
            len++;
            cur = cur.getNext();
        }
        int n = len / k; // 计算出有几组
        LinkedNode pre = dummyNode;
        cur = head;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k - 1; j++) {
                LinkedNode next = cur.getNext();
                cur.setNext(cur.getNext().getNext());
                next.setNext(pre.getNext());
                pre.setNext(next);
            }
            pre = cur;
            cur = cur.getNext();
        }
        return dummyNode.getNext();
    }
/**
* 穿针引线法
*/
    public static LinkedNode TheSecondMethod(LinkedNode head, int k) {
        LinkedNode dummyNode = new LinkedNode(0);
        dummyNode.setNext(head);
        LinkedNode pre = dummyNode;
        LinkedNode end = dummyNode;
        while (end.getNext() != null) {
            // 找到要处理的区间的末尾
            for (int i = 0; i < k && end != null; i++) {
                end = end.getNext();
            }
            if (end == null) {
                break;
            }
            // 将要处理的区间裁剪下来
            LinkedNode start = pre.getNext();
            LinkedNode next = end.getNext();
            end.setNext(null);
            // 执行反转
            pre.setNext(reverse(start));
            start.setNext(next);
            // 调整指针，为下一组做准备
            pre = start;
            end = pre;
        }
        return dummyNode.getNext();
    }

    private static LinkedNode reverse(LinkedNode head) {
        LinkedNode pre = null;
        LinkedNode cur = head;
        while(cur!= null){
            LinkedNode next = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        int[] vars = {1, 3, 4, 5, 7, 8, 9};
        LinkedNode head = LinkedNode.initList(vars);
        LinkedNode.printLinkedList(TheSecondMethod(head, 4));
    }
}

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

链表

package AlgorithmFirst;

public class LinkedNode {
    private int data;
    private LinkedNode next;

    public LinkedNode(int data) {
        this.data = data;
    }

    /**
     * 获取数据
     *
     * @return 数据值
     */
    public int getData() {
        return this.data;
    }

    /**
     * 设置数据的值
     *
     * @param data 数据
     */
    public void setData(int data) {
        this.data = data;
    }

    /**
     * 获取下一个节点
     *
     * @return 当前节点的下一个几点
     */
    public LinkedNode getNext() {
        return this.next;
    }

    /**
     * 设置下一个节点的值
     *
     * @param next 下一个节点
     */
    public void setNext(LinkedNode next) {
        this.next = next;
    }

    /**
     * 获取链表长度
     *
     * @param head 头节点
     * @return
     */
    public static int getListLength(LinkedNode head) {
        int length = 0;
        LinkedNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 缺省位置，直接在最后插入
     *
     * @param head       头节点
     * @param insertNode 插入节点
     * @return 头节点
     */
    public static LinkedNode insertNode(LinkedNode head, LinkedNode insertNode) {
        int size = getListLength(head);
        // return insertNode(head,insertNode,size+1); 修改一下，以便insertNode后面的元素能够全部插入进来。
        int count = 1;
        LinkedNode temp = head;
        if (head == null) {
            return insertNode;
        }
        while (temp != null) {
            if (count == size) {
                temp.next = insertNode;
                temp = null;
            } else {
                temp = temp.next;
                count++;
            }
        }
        return head;
    }

    /**
     * 指定位置插入
     *
     * @param head       头节点
     * @param nodeInsert 插入节点
     * @param position   插入位置，从1开始
     * @return 返回头节点
     */
    public static LinkedNode insertNode(LinkedNode head, LinkedNode nodeInsert, int position) {
        if (head == null) {
            // 如果head == null 表示当前链表为空，可以直接返回当前节点，或者报异常，这里直接把它当作头节点。
            return nodeInsert;
        }
        // 已经存在的元素的个数
        int size = getListLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        // 表头插入
        if (position == 1) {
            nodeInsert.next = head;
            // 这里可以直接 return nodeInsert
            head = nodeInsert;
            return head;
        }

        LinkedNode pNode = head;
        int count = 1;
        // 这里position 被上面的size限制住了，不用考虑pNode = null
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;
    }

    /**
     * 缺省参数的删除最后一个节点
     *
     * @param head 链表头节点
     * @return 返回新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head) {
        int size = getListLength(head);
        return deleteNode(head, size);
    }

    /**
     * 根据位置删除节点
     *
     * @param head     链表头节点
     * @param position 位置从1开始，最大链表大小 超出不删除，返回原头节点。
     * @return 新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head, int position) {
        if (head == null) {
            // 链表为空，无法删除
            return null;
        }
        int size = getListLength(head);
        if (position > size || position < 1) {
            System.out.println("输入参数有误");
            return head;
        }
        if (position == 1) {
            return head.next;
        } else {
            LinkedNode cur = head;
            int count = 1;
            while (count < position - 1) {
                cur = cur.next;
                count++;
            }
            LinkedNode curNode = cur.next;
            cur.next = curNode.next;
            //上面两行可以简化成 ： cur.next = cur.next.next
        }
        return head;
    }

    public static LinkedNode initList(int[] vals) {
        LinkedNode head = null;
        for (int val : vals) {
            head = insertNode(head, new LinkedNode(val));
        }
        return head;
    }

    public static void printLinkedList(LinkedNode head) {
        int count = 0;
        while (head != null) {
            System.out.println("第 " + ++count + " 个：" + head.data);
            head = head.next;
        }
    }

    public static void main(String[] args) {
        LinkedNode head = new LinkedNode(0);
        for (int i = 0; i < 10; i++) {
            head = LinkedNode.insertNode(head, new LinkedNode(i + 1));
        }
        System.out.println("origin:");
        printLinkedList(head);
        head = deleteNode(head, 3);
        System.out.println("delete the third ");
        printLinkedList(head);
        head = deleteNode(head);
        System.out.println("delete the last one");
        printLinkedList(head);
        head = insertNode(head, new LinkedNode(11));
        System.out.println("insert one from last");
        printLinkedList(head);
        head = insertNode(head, new LinkedNode(22222), 1);
        System.out.println("insert to first");
        printLinkedList(head);
    }

}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

近期在自学 Java 做项目，加入了一个编程学习圈子，里面有编程学习路线和原创的项目教程，感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑，也希望能对大家有帮助，扫 ⬇️ 二维码即可加入。

也可以点击链接：我正在「编程导航」和朋友们讨论有趣的话题，你⼀起来吧？