(17)Go反转链表和删除链表倒数第n个节点

1）反转链表

解答思路如下图示：

// 时间复杂度O(n)
// 空间复杂度O(1)
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head

    for cur != nil {
        next := cur.Next

        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

提交leetcode，通过

2）删除链表倒数第n个节点

一趟扫描的实现方法
思路：定义2个索引p和q，p，q距离相差n+1个节点距离，因为链表最后一个节点是nil，
当q==nil时，p的下一个节点p.Next为要删除的节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 虚拟头结点
    dummyHead := &ListNode{Next: head}

    p, q := dummyHead, dummyHead

    for i := 0; i < n+1; i++ {
        q = q.Next
    }

    for q != nil {
        p = p.Next
        q = q.Next
    }
    p.Next = p.Next.Next

    return dummyHead.Next
}

提交leetcode，通过