The first question is to delete the penultimate node of the linked list

Topic information

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.

Problem solving ideas

1. To delete the nth node, we only need to set a pointer, locate it to the previous node of N, and then change its next pointer to point to the next node of n.
2. Considering that the length of the linked list may be 1 and the previous node cannot be located, we introduce a new concept

The code is as follows

func getLength(head *ListNode) (length int) {
    for ; head != nil; head = head.Next {
        length++
    }
    return
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getLength(head)
    dummy := &ListNode{0, head}
    cur := dummy
    for i := 0; i < length-n; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
    return dummy.Next
}

Complexity analysis

Time complexity: O(L+n), where l is the length of the linked list.

Space complexity: O(1).

Another way is to use the pointer

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    first, second := head, 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
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

Double pointer is a cool, powerful and common problem solving tool

Complexity analysis

Time complexity: O(L), where l is the length of the linked list.

Space complexity: O(1).

Question 2 reverse linked list

Topic information

Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.

Problem solving ideas

The simplest and most violent idea is, of course
Use two pointers to point to the head and tail of the linked list respectively, and move to the middle of the linked list together to exchange their values one by one

code

func getLength(head *ListNode) (length int) {
    for ; head != nil; head = head.Next {
        length++
    }
    return
}
func reverseList(head *ListNode) *ListNode {
    dummy := head//Point to head node
    length := getLength(head)
    tail := dummy    //Point to tail node
    for i := 0; i < length-1; i++ {
        tail = tail.Next
    }
    for i:=0;i<length/2;i++{
        dummy.Val,tail.Val=tail.Val,dummy.Val
        dummy=dummy.Next
        tail = dummy    //Point to tail node
        for j := 0; j < length-3-2*i; j++ {
            tail = tail.Next
        }
    }
    return head
}

Complexity analysis

Time complexity: O (8/3n^2) = O (n^2) each time the exchange is completed, it is necessary to find the position of tail again. The length of the search is from n/2 to N, and N is the length of the linked list
Space complexity: O (1)

optimization

Obviously, because the single linked list can't search forward, we have done a lot of meaningless work when positioning forward. Such operation efficiency can't satisfy us.
Check the official answer, and the optimization is as follows

Use an auxiliary node to store the previous node, and choose to change the pointer to exchange nodes, which makes the exchange more convenient
The code is as follows

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

In addition, there is a recursive solution, which is relatively complex compared with iteration

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

Complexity analysis
iteration
Time complexity: O(n), where n is the length of the linked list. You need to traverse the linked list once.
Space complexity: O(1).
recursion
Time complexity: O(n), where n is the length of the linked list. You need to reverse each node of the linked list.
Spatial complexity: O(n), where n is the length of the linked list. The space complexity mainly depends on the stack space of recursive calls, up to N layers.


The operation efficiency has been significantly improved