leetcode-go/hard/25.go

package main

import "fmt"

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k <= 1 {
		return head
	}
	beforeBeg, beg, end, afterEnd := (*ListNode)(nil), head, head, head.Next
	for end.Next != nil {
		counter := 1
		for end.Next != nil && counter < k {
			end = end.Next
			afterEnd = end.Next
			counter++
		}
		if counter != k {
			// Dont need to reverse
			return head
		}
		// Reverse k node from beg to end
		prev, curr, next := beforeBeg, beg, beg.Next
		// Reverse all link between beforBeg & afterEnd
		for i := 1; i < k; i++ {
			prev = curr
			curr = next
			next = next.Next
			curr.Next = prev
		}
		if beforeBeg == nil {
			head = end
		} else {
			beforeBeg.Next = end
		}
		beg.Next = afterEnd
		// Update anchor node
		beforeBeg = beg
		beg = beforeBeg.Next
		end = beg
		if end == nil {
			return head
		}
		afterEnd = end.Next
	}
	return head
}

func main() {
	// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
	n7 := ListNode{7, nil}
	n6 := ListNode{6, &n7}
	n5 := ListNode{5, &n6}
	n4 := ListNode{4, &n5}
	n3 := ListNode{3, &n4}
	n2 := ListNode{2, &n3}
	n1 := ListNode{1, &n2}
	fmt.Println(list2str(&n1))
	fmt.Println(list2str(reverseKGroup(&n1, 5)))
	// 0
	n0 := ListNode{0, nil}
	fmt.Println(list2str(reverseKGroup(&n0, 1)))
}