目录
链表K位翻转
访问量:1357

一、简介

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表

如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样

你不能更改节点中的值,只能更改节点本身。


二、代码实现

思路: 分治 + 链表逆转

type ListNode struct {
   Val  int
   Next *ListNode
}


/**
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
func reverseKGroup( head *ListNode ,  k int ) *ListNode {
   if  head == nil {
       return head
   }
   tailNode := head
   for i:=0; i< k; i++ {
      // 若 不够 k个元素,不逆转
      if tailNode == nil {
         return head
      }

      tailNode = tailNode.Next
   }

   newHead := reverseList(head, tailNode)
   head.Next = reverseKGroup(tailNode, k)

   return newHead
}

// 逆转 firstNode ~ lastNode之间的节点
func reverseList(firstNode, lastNode *ListNode) *ListNode {
   var newHead *ListNode

   for firstNode != lastNode {
      nextNode := firstNode.Next
      firstNode.Next = newHead

      newHead = firstNode
      firstNode = nextNode
   }

   return newHead
}

 

题目来源:牛客