Topic:

Ideas:

  • Declare an empty node (pre), representing the previous node
  • The variable cur represents the first node

Start:

  1. Save the “location” of the second node to a temporary variable, to prevent 1 and 2 nodes from being found after disconnection;
  2. Next of the first node in cur points to pre, which completes the flip of 1 node.
  3. Pre and CUR move backward by one node each;
  4. Repeat the above three steps to complete the node flip in turn;

Core code:

// Reverse the implementation of the linked list
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode = nil
	cur := head
	forcur ! =nil {
		nextTemp := cur.Next //1. Save the next node as a temporary variable to prevent the following overwrite loss
		cur.Next = pre       //2. The current node points to the former node, and the current node completes the transformation
		pre = cur            //3. The former node changes to the current node to prepare for the next node transformation
		cur = nextTemp       //4. The current node changes to the next node to prepare for the next node transformation
		Next = cur, cur.Next, pre
	}
	return pre
}
Copy the code

Full code demo:

package main

import "fmt"

// Linked list node
type ListNode struct {
	Val  int
	Next *ListNode
}

// Reverse the implementation of the linked list
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode = nil
	cur := head
	forcur ! =nil {
		nextTemp := cur.Next //1. Save the next node as a temporary variable to prevent the following overwrite loss
		cur.Next = pre       //2. The current node points to the former node, and the current node completes the transformation
		pre = cur            //3. The former node changes to the current node to prepare for the next node transformation
		cur = nextTemp       //4. The current node changes to the next node to prepare for the next node transformation
		Next = cur, cur.Next, pre
	}
	return pre
}

func main(a) {
	head := new(ListNode)
	head.Val = 1
	ln2 := new(ListNode)
	ln2.Val = 2
	ln3 := new(ListNode)
	ln3.Val = 3
	ln4 := new(ListNode)
	ln4.Val = 4
	ln5 := new(ListNode)
	ln5.Val = 5
	head.Next = ln2
	ln2.Next = ln3
	ln3.Next = ln4
	ln4.Next = ln5

	this1 := head
	forthis1 ! =nil {
		fmt.Println(this1.Val)
		this1 = this1.Next
	}

	pre := reverseList(head)
	fmt.Println("After flipping:")
	this2 := pre
	forthis2 ! =nil {
		fmt.Println(this2.Val)
		this2 = this2.Next
	}
}
Copy the code

Running result:

1
2
3
4
5After the turn:5
4
3
2
1
Copy the code