234. Palindrome Linked List

Easy

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

这是一道经典的回文题，难度在于要求用O(1)空间复杂度，因此不能用栈之类的辅助数据结构。这里的思路是，将后半段链表反转，然后一一比较前后半段链表的。需要处理的是，链表的长度为偶数是，中间节点要参与比较，否则不用。

func isPalindrome(head *ListNode) bool {
    reverse := func(h *ListNode) *ListNode {
        if h == nil || h.Next == nil {return h}
        var pre, cur *ListNode = nil, h
        for cur != nil {
            nxt := cur.Next //pre -> cur -> nxt
            cur.Next = pre //pre <- cur -> nxt
            pre = cur
            cur = nxt //xx <- pre -> cur
        }
        return pre
    }
    
    //find the mid node as well as the odd/even of list
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    //list len is odd num
    if fast != nil {slow = slow.Next}
    slow = reverse(slow) //reverse the second half of list
    //compare the first half and second half of list
    for slow != nil {
        if head.Val != slow.Val {return false}
        head = head.Next
        slow = slow.Next
    }
    return true
}

测试一下

Success
[Details]
Runtime: 12 ms, faster than 99.70% of Go online submissions for Palindrome Linked List.
Memory Usage: 5.9 MB, less than 95.70% of Go online submissions for Palindrome Linked List.

725. Split Linked List in Parts

Medium

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts".

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode's representing the linked list parts that are formed.
Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Example 1:

Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:
The length of root will be in the range [0, 1000].
Each value of a node in the input will be an integer in the range [0, 999].
k will be an integer in the range [1, 50].

题目要求将链表平均地分为k份，最长的链表和最短链表的长度差不超过1。分解链表不复杂，关键在于分解的长度要平均，用取模的方法，将模数分配到每一个子链表中。

func splitListToParts(head *ListNode, k int) (parts []*ListNode) {
    var size int
    var prev, cur *ListNode = nil, head
    for ;cur != nil; size++ {cur = cur.Next}
    length := size/k
    remain := size%k //split length of nodes as well as remain of nodes
    // to parts
    parts = make([]*ListNode, k)
    for i := 0; i < k; i++{
        var remainToAdd int
        if remain > 0 {remainToAdd = 1}//need to split a remain
        parts[i] = head //record one head of parts
        for j := 0; j < length + remainToAdd; j++{
            prev = head
            head = head.Next
        }
        if prev != nil {prev.Next = nil}//end of part list
        remain--
    }
    return
}

测试一下

Success
[Details]
Runtime: 4 ms, faster than 21.21% of Go online submissions for Split Linked List in Parts.
Memory Usage: 3.2 MB, less than 100.00% of Go online submissions for Split Linked List in Parts.