Leetcode 25 Reverse Nodes in k-Group 题解分析

发表于 更新于 分类于 ， 阅读次数： 阅读次数： Disqus：

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.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

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

这个题也算是经典中的经典了，各种算法题中的保留曲目，可能不全一样，不过反正都是逆转，这个算是比较难度大的，普通的应该就是整个链表反转，或者只对一个链表中的 m 到 n 位做翻转，这里是 k 个一组做翻转，其实这道题比较难的点是两个，一个是想清楚怎么处理，一个是代码的处理
简单来看下

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
public ListNode reverseKGroup(ListNode head, int k) {
    if (k <= 1) {
        return head;
    }
    if (head == null) {
        return null;
    }
    ListNode tempEnd = head;
    ListNode tempHead = head;
    ListNode lastHead = null;
    boolean isHeadSet = false;
    while (true) {
        // k 个一组获取头尾
        for (int i = 0; i < k - 1; i++) {
            System.out.println(tempEnd.val);
            if (tempEnd.next != null) {
                tempEnd  = tempEnd.next;
            } else {
                tempEnd = null;
                break;
            }
        }
        if (tempEnd != null) {
            if (!isHeadSet) {
                // 只有在第一组返回的时候需要赋值给 head
                head = reverse(null, tempHead, tempEnd);
                isHeadSet = !isHeadSet;
            } else {
                // 后面的需要将前一组的尾巴传进去，作为后一组头
                reverse(lastHead, tempHead, tempEnd);
            }
            if (tempHead.next != null) {
                // 如果后续节点还有
                lastHead = tempHead;
                tempEnd = tempHead.next;
                tempHead = tempHead.next;
            } else {
                break;
            }
        } else {
            break;
        }
    }

    return head;
}
public ListNode reverse(ListNode lastHead, ListNode tempHead, ListNode tempEnd) {
    // k 个一组的头尾传进来
    ListNode tail = null;
    while (tail != tempEnd) {
        // tail 表示是将头往后换时，把后面那个先拿着
        tail = tempHead.next;
        // 然后就是交换
        tempHead.next = tempEnd.next;
        tempEnd.next = tempHead;
        tempHead = tail;
    }
    if (lastHead !=null) {
        // 如果不是第一组，则需要接上前一组的尾巴
        lastHead.next = tail;
    }
    return tail;
}