题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here if head==None or head.next==None or k==1: return head count=0 ptr=head while ptr: count+=1 ptr=ptr.next print(count,head.val) res=ListNode(-1) res.next=head pre=res cur=head for _ in range(count//k): for _ in range(k-1): temp=cur.next cur.next=temp.next temp.next=pre.next pre.next=temp pre=cur cur=cur.next return res.next
Python版本实现。官方解答看起来相比翻转[m,n]区间的版本,只给了递归解答,其实[m,n]版本是完全可以拿过来套用的。
- 1.首先遍历链表获取总长度count
- 2.双层循环:(1)第一层循环count//k次,也就是“k个一组”有几组;(2)第二层和[m,n]版本一样,翻转链表的一部分。
- 3.需要注意的是,翻转完毕每k个节点后,按照[m,n]版本官方解答的做法,pre仍然指向从这k个节点的第一个节点,再往前一个节点;而cur指向的则是这k个节点中的最后一个节点。所以说,处理下一组k个节点时,只需要把pre指向现在的cur,cur再前进一个就可以啦!