Table of Contents
Reverse Linked List
Problem Statment
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?
Iterative Approach
Golang solution
/**
* 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
}
previous := head
current := head.Next
for current != nil {
next := current.Next
// reverse a pointer from 2nd element
current.Next = previous
// move all pointer by 1
previous = current
current = next
}
// original head’s next needs updation to nil
head.Next = nil
head = previous
return head
}
Output
head =
[1,2,3,4,5]
Output
[5,4,3,2,1]
Recursive Approach
Golang Solution
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
// recursion approach
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
// when we reach 2nd last node
// perform reversal operation
head.Next.Next = head
head.Next = nil
return newHead
}
Output
Visit https: https://codeandalgo.com for more such contents
Leave a Reply