数据结构(3): 链表

3.1 删除单向链表倒数第n个节点

问题描述：删除单向链表倒数第n个节点（只遍历一次）
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

思路：两个指针，p1先走n步，然后p1和p2再一起走，当p1到链表结尾，p2就是要删除的节点。注意处理可能删除的是头结点（n=length）或者不需要删除（n>length）的情况。
可以通过增加一个虚拟的头节点，避免对头节点的特殊处理。

示例代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    p1, p2 := head, head
    i := 0
    for ; i < n && p1 != nil ; i++ {
        p1 = p1.Next
    }
    if p1 == nil {
        if i < n {
            // 不需要删除
            return head
        } else {
            // 删除头节点
            return head.Next
        }
    }
    for p1.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    t := p2.Next
    if t != nil {
        p2.Next = t.Next
    }
    return head
}

3.2 K个一组翻转链表

LeetCode No.25

题目描述：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路： 先遍历一遍求出链表长度n，则需要翻转n/k组。使用一个虚拟头节点保存结果，每一轮翻转完将尾节保存，下一轮翻转结束后将上一轮的为节点的Next节点指向当前轮的头结点。

示例代码：

func reverseKGroup(head *ListNode, k int) *ListNode {
    n := 0
    for p := head; p != nil; p = p.Next {
        n++
    }
    reshead := &ListNode{}
    var lasttail *ListNode
    for i, p := 0, head; i <= n/k; i++ {
        if i == n / k {
            lasttail.Next = p
            break
        }
        curhead, curtail := p, p
        for j := 0; j < k; j++ {
            tmp := p
            p = p.Next
            tmp.Next = curhead
            curhead = tmp
        }
        if i == 0 {
            reshead.Next = curhead
        } else {
            lasttail.Next = curhead
        }
        lasttail = curtail
    }
    return reshead.Next
}