[Go] Linked List - Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

 

Mycode

func reverseList(head *ListNode) *ListNode {
	end := head
	reverse := head
	if head == nil{
		return head
	}
	for end.Next != nil {
		end = end.Next
	} 

	new := &ListNode{Val: end.Val, Next: nil}
	for reverse.Next != nil {
		buf := new.Next
		n := &ListNode{Val: reverse.Val, Next: buf}
		new.Next = n
		reverse = reverse.Next
	}

	return new
}

https://go.dev/play/p/QcV7pnJujM4

• For me, Making new Linked list is easiest way to solve problem.
• I need to refer other people's code.
• But it doesn't have many differences about 

 

sample 0 ms submission

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{ 
        return head
    }
    
    cur := head
    var reversed *ListNode
    for (cur != nil) {
        temp := cur.Next
        cur.Next = reversed
        reversed = cur
        cur = temp
    }
    return reversed
    
}

• This code use temp and reverse.
• cur.Next address will hand to temp.
• reserved address will hand to cur.Next
• cur address will hand to reversed.
• temp will hand address to cur.
• when cur is empty, for loop will end.
• I don't think this is effective way.

sample 1 ms submission

func reverseList(head *ListNode) *ListNode {
	// base case
	if head == nil || head.Next == nil {
		return head
	}
	// 递归已经帮你反转了 head 之后的所有节点，并返回反转后的头节点 last
	// 你需要做的就是把当前节点 head 和反转后的链表链接起来即可。
	last := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return last
}

• It was hard to understand because i don't know what last returns.
• see below picture.
•  

sample 2 ms submission

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

sample 3 ms submission & sample 2500 KB submission

func reverseList(head *ListNode) *ListNode {
    
    if head == nil || head.Next == nil {
        return head
    }
    
  var prev *ListNode
  for head != nil {
      tempNext := head.Next
      head.Next = prev
      prev = head
      head = tempNext
  }

  return prev
}

sample 4 ms submission & sample 2600 KB submission

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

sample 5 ms submission

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
}

sample 6 ms submission & sample 2800 KB submission

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
    
}

sample 2700 KB submission

func reverseList(head *ListNode) *ListNode {
    curr := head
	var newList *ListNode = nil

	for curr != nil {
		
		

		newList = &ListNode{
			Val:  curr.Val,
			Next: newList,
		}

		curr = curr.Next

	}

	return newList
}

• This code has same concept with me.