Reverse partial linked list golang

Reversing a linked list is a classic problem, it is widely used, the time complexity is not high, and it is not difficult to implement. This article will introduce how to implement an algorithm for reversing a partial linked list in golang.

Reverse the linked list

Let’s first look at how to reverse the linked list. We can implement it in two ways: iteration or recursion.

1. Iteration method

We use three pointers pre, cur, and next to iteratively perform the reversal operation, where pre and next are to save the predecessor and successor of cur. nodes for easy reconnection after reversal. The code is as follows:

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
}

2. Recursive method

Although the recursive method is not as easy to understand as the iterative method, it is actually a good example of practicing recursive thinking. What needs to be noted in the recursive operation is that after recursing to the end of the linked list, the tail node needs to be assigned to the Next node of the head, and then the tail node is returned as the new head. The code is as follows:

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

Reverse the partial linked list

With the foundation of reversing the linked list, let's take a look at how to reverse the partial linked list. The description of the problem is as follows:

Given a linked list and two integers m and n, reverse the linked list from position m to n. It is required to give an algorithm implementation.

By observing the question, we can split it into three parts for consideration:

1. Before m: There is no need to reverse the linked list
2. m to n Between: Need to reverse the linked list
3. n After: No need to reverse the linked list

Therefore, we need to use pre and tail variables to record the tail node of the first part and the second part head node, and then reverse the second part. After reversing, connect the tail node of the first part and the head node of the second part.

The code is as follows:

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m <= 0 || n < m {
        return head
    }
    
    // 特判，如果m=1，则不需要第一部分
    if m == 1 {
        return reverseN(head, n)
    }
    
    //  遍历到m-1位置，记录pre和tail
    var pre *ListNode = nil
    cur := head
    for i := 1; i < m; i++ {
        pre = cur
        cur = cur.Next
    }

    tail := cur // tail 记录第一部分的末尾是 cur             
    // 将第二部分进行反转操作
    new_head := reverseN(cur, n - m + 1)

    // 将第一部分与第二部分重新连接
    tail.Next = new_head
    if pre != nil {
        pre.Next = tail
        return head
    } else {
        return tail
    }
}

// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }
    if n == 1 {
        return head
    }
    var pre *ListNode = nil
    cur := head
    for i := 1; i <= n && cur != nil; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    head.Next = cur
    return pre
}

Summary

Reversed linked list is a frequent visitor to linked list interview questions. Mastering this algorithm idea can not only solve the problem of inverted linked list, but also expand Transform operations to other linked lists. When conducting interviews, the inverted linked list may be used as an example for other questions, which is very important for developing ideas. To implement the reverse linked list and partial linked list algorithms in golang, you need to pay attention to the use of pointers, Nil judgment and other issues. After mastering the code, it is very simple to implement.

The above is the detailed content of Reverse partial linked list golang. For more information, please follow other related articles on the PHP Chinese website!