“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Reverse a linked list

Reverse linked lists

Topic describes

Given the head node of a single linked list, reverse the list and return the reversed list

The sample

Example 1

Input: head = [1,2,3,4,5] output: [5,4,3,2,1]Copy the code

Example 2

Input: head = [1,2] output: [2,1]Copy the code

Example 3

Input: head = [] Output: []Copy the code

Tip:

  • The number of nodes in a linked list ranges from[0, 5000]
  • 5000 <= Node.val <= 5000

The problem solving

Solution one: reverse in place

Train of thought

Reverse in place method, find an empty node to act as a new head node (similar to the sentinel), then traverse each node in the list to be reversed, each traversed node is inserted after the new head node, the process is as follows:

The main thing is to insert every node that you walk through behind the sentinel node

code

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil{ return head } newHead := &ListNode{} newHead.Next = head prevNode := newHead.Next currentNode := prevNode.Next for currentNode ! = nil { prevNode.Next = currentNode.Next currentNode.Next = newHead.Next newHead.Next = currentNode currentNode = prevNode.Next } head = newHead.Next return head }Copy the code

The execution result

Solution two: head insertion method

Train of thought

This method is relatively simple. It is to create a new linked list and insert each node of the linked list to be reversed into the new linked list by way of header insertion

code

Func (list * list) ReverseListHead() {if list.headNode == nil {ftt.println (" list is empty ") return} newList := & list {} currentNode := list.headNode nextNode := currentNode.Next for currentNode! =nil { if newList.headNode == nil { newList.headNode = currentNode newList.headNode.Next = nil currentNode = nextNode continue } nextNode = currentNode.Next currentNode.Next = newList.headNode newList.headNode = currentNode currentNode = NextNode} FMT.Println(" after ") newlist.traverse ()}Copy the code