https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
# -*- coding:utf-8 -*- # Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution: def reverseKGroup(self, head: ListNode, k: int): """ :type head: ListNode :type k: int :rtype: ListNode """ cur = head count = 0 while cur and count != k: cur = cur.next count += 1 if count == k: cur = self.reverseKGroup(cur, k) while count: tmp = head.next head.next = cur cur = head head = tmp count -= 1 head = cur return head if __name__ == '__main__': n1 = ListNode(1) n2 = ListNode(2) n3 = ListNode(3) n4 = ListNode(4) n5 = ListNode(5) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 print(Solution().reverseKGroup(n1, 5))
思路:这道题刚开始我的思路是交换,也就是说交换0和k-1个链表,然后是1和k-2一直到中间位置,然后向下递归,后来发现这个方法实现起来有一定难度,因为这个链表是单向链表,无法向前找k-2节点,而每次都遍历查找的代价有有点高,因此采用移动而不是交换的方法来进行交换。简单说就是每次都将不在交换序列中的链表(也就是不是前k个以及已经交换过的节点)扔到头结点的后面,这样头节点就后移了,也就进行交换了。(简单图示如下,瞎画凑合看emm)

思考:还有一个比较好的思路就是用栈,免去了链表连来连去的问题。
栈的特性,先进后出刚好满足交换原则,1234进栈出栈则为4321,因此将链表依次入栈,出栈之后依次链起来即可。
0 条评论