1）反轉(zhuǎn)鏈表
解答思路如下圖示：
// 時間復(fù)雜度O(n)
// 空間復(fù)雜度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）刪除鏈表倒數(shù)第n個節(jié)點
一趟掃描的實現(xiàn)方法
思路：定義2個索引p和q，p葛账，q距離相差n+1個節(jié)點距離，因為鏈表最后一個節(jié)點是nil皮仁，
當(dāng)q==nil時籍琳，p的下一個節(jié)點p.Next為要刪除的節(jié)點
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 虛擬頭結(jié)點
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，通過
