19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
题解
思路：
1.计算链表长度
1.计算链表长度 2.增加一个哑节点，遍历到倒数n+1的位置
2.栈存储节点
1.存储所有节点 2.倒数n+1的节点就是nodes[len(nodes)-1-n]
3.双指针
1.两个指针，步伐相同 2.快指针先移动n步 3.两个指针一起移动，直到快指针为nil 4.此时慢指针就是倒数n位置
代码
func removeNthFromEnd(head *ListNode, n int) *ListNode { //计算链表长度 length := getLength(head) dummy := &ListNode{ Val: 0, Next: head, } cur := dummy //遍历到倒数n+1的位置 for i := 0; i < length-n; i++ { cur = cur.Next } //去除倒数n cur.Next = cur.Next.Next return dummy.Next } func getLength(head *ListNode) (ans int) { for head != nil { ans++ head = head.Next } return ans }
func removeNthFromEnd(head *ListNode, n int) *ListNode { var nodes []*ListNode dummy := &ListNode{ Val: 0, Next: head, } //存储所有节点 for node := dummy; node != nil; node = node.Next { nodes = append(nodes, node) } //找出倒数n+1的节点 prev := nodes[len(nodes)-1-n] prev.Next = prev.Next.Next return dummy.Next }
func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{ Val: 0, Next: head, } first := head second := dummy for i := 0; i < n; i++ { first = first.Next } for first != nil { first = first.Next second = second.Next } second.Next = second.Next.Next return dummy.Next }
