leetcode-025-Reverse-Nodes-in-k-Group

发表于 | 更新于: | 分类于 |

1. 题目

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

示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

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

2. 解

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
	# k=1时为原链表
        if k == 1:
            return head
        
	# c遍历链表，为当前结点
        c = head
		
	# 用tot算出总节点数，知道什么时候该停止
        tot = 0
        p = head
        while p:
            p = p.next
            tot += 1
            
	# cnt表示目前为止一共reverse了几个节点
        cnt = 0
		
	#从头部开始遍历
        while c:
		
		#判断翻转K个是否越界
            if cnt + k <= tot:
				
			#分情况讨论，如果是第一次reverse，那么直接返回原始链表的head
                if cnt == 0:
				# 这里需要注意的是，第一次反转，记得使用原始链表的头结点head
                    head = self.reverse(c,k)
                    cnt += k
                else:
				# 如果不是第一次反转
				# 这里有个巧妙的地方，当我们进行完第一次后，c指向第一个reverse区间的最后一个节点
				# 所以需要反转c.next为头的子链表
				# 这里用临时的头结点head_k替代c遍历链表
                    head_k = c.next
				# 用临时的新头结点指向反转好的子链表
                    new_head = self.reverse(head_k,k)
                    cnt += k
				# 将之前的链表和反转好的子链表接起来
                    c.next = new_head
				# 反转结束后，临时的头结点head_k指向子链表的末尾，重置c的位置
                    c = head_k
					
		#越界就说明我们已经reverse了能reverse的部分，直接退出
            else:
                break

        return head
    
# 206反转链表（代码思路一模一样）
# 需要注意的是，N个结点的需要反转N-1次
    def reverse(self,head_k,k):
		#记录目前reverse的数量
        count = 1
        new_head = head_k
        while count < k:
            t = head_k.next
            head_k.next = head_k.next.next
            t.next = new_head
            new_head = t
            count += 1
        return new_head