25. Reverse Nodes in k-Group

Hard

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

这是反转链表系列的终极BOSS，将链表按每K个节点反转。我们需要维持一个节点的索引，将每K个节点作为起始，反转之后的链表。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k == 1 {return head}
    dummy := ListNode{Next:head}
    var size int
    //measure the length of list
    for head != nil {
        head = head.Next
        size++
    }
    pre := &dummy
    for seg := 0; seg + k <= size; seg += k {
        cur := pre.Next
        nxt := cur.Next
        for i := 1; i < k; i++ {
            /*
                pre -> cur -> nxt -> nn
                cur -> nn
                nn  -> cur
                nxt  -> cur(pre) - > nn(nxt)
            */
            //swap cur and nxt, put nxt before cur
            cur.Next = nxt.Next 
            nxt.Next = pre.Next //this must be 'pre.Next' rather than 'cur'
            pre.Next = nxt //link new head
            nxt = cur.Next //advance to next
        }
        pre = cur
    }

    return dummy.Next
}

测试一下

Success
[Details]
Runtime: 4 ms, faster than 99.02% of Go online submissions for Reverse Nodes in k-Group.
Memory Usage: 3.6 MB, less than 98.26% of Go online submissions for Reverse Nodes in k-Group.

148. Sort List

Medium

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

这道题经常见到，其中需要用到很多链表的操作方法。

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {return head}
    fast, slow := head.Next, head //fast need always ahead of slow
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    mid := slow.Next
    slow.Next = nil
    return sortListMerge(sortList(head), sortList(mid))
}

func sortListMerge(head1, head2 *ListNode) *ListNode {
    dummy := &ListNode{}
    pre := dummy
    for head1 != nil && head2 != nil {
        if head1.Val <= head2.Val {
            pre.Next = head1
            head1 = head1.Next
        } else {
            pre.Next = head2
            head2 = head2.Next          
        }
        pre = pre.Next
    }

    if head1 != nil {
        pre.Next = head1
    } else if head2 != nil {
        pre.Next = head2
    }
    return dummy.Next
}

测试一下

Success
[Details]
Runtime: 12 ms, faster than 92.86% of Go online submissions for Sort List.
Memory Usage: 5 MB, less than 97.86% of Go online submissions for Sort List.