Given pointer to the head node of a linked list, the task is to reverse the linked list.

Examples:

Input : Head of following linked list  
       1->2->3->4->NULL
Output : Linked list should be changed to,
       4->3->2->1->NULL

Input : Head of following linked list  
       1->2->3->4->5->NULL
Output : Linked list should be changed to,
       5->4->3->2->1->NULL

Input : NULL
Output : NULL

Input  : 1->NULL
Output : 1->NULL
[ad type=”banner”]

Iterative Method
Iterate trough the linked list. In loop, change next to prev, prev to current and current to next

Python Programming:

[pastacode lang=”python” manual=”%23%20Python%20program%20to%20reverse%20a%20linked%20list%20%0A%23%20Time%20Complexity%20%3A%20O(n)%0A%23%20Space%20Complexity%20%3A%20O(1)%0A%20%0A%23%20Node%20class%20%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20initialize%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20reverse%20the%20linked%20list%0A%20%20%20%20def%20reverse(self)%3A%0A%20%20%20%20%20%20%20%20prev%20%3D%20None%0A%20%20%20%20%20%20%20%20current%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while(current%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20current.next%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20prev%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20next%0A%20%20%20%20%20%20%20%20self.head%20%3D%20prev%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20Function%20to%20insert%20a%20new%20node%20at%20the%20beginning%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20%23%20Utility%20function%20to%20print%20the%20linked%20LinkedList%0A%20%20%20%20def%20printList(self)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while(temp)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20functions%0Allist%20%3D%20LinkedList()%0Allist.push(20)%0Allist.push(4)%0Allist.push(15)%0Allist.push(85)%0A%20%0Aprint%20%22Given%20Linked%20List%22%0Allist.printList()%0Allist.reverse()%0Aprint%20%22%5CnReversed%20Linked%20List%22%0Allist.printList()%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)” message=”” highlight=”” provider=”manual”/]
Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85

Time Complexity: O(n)
Space Complexity: O(1)

[ad type=”banner”]

Recursive Method:

   1) Divide the list in two parts - first node and rest of the linked list.
   2) Call reverse for the rest of the linked list.
   3) Link rest to first.
   4) Fix head pointer

Write a function to reverse a linked list

C Programming:

[pastacode lang=”c” manual=”void%20recursiveReverse(struct%20node**%20head_ref)%0A%7B%0A%20%20%20%20struct%20node*%20first%3B%0A%20%20%20%20struct%20node*%20rest%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%2F*%20empty%20list%20*%2F%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20return%3B%20%20%20%0A%20%0A%20%20%20%20%2F*%20suppose%20first%20%3D%20%7B1%2C%202%2C%203%7D%2C%20rest%20%3D%20%7B2%2C%203%7D%20*%2F%0A%20%20%20%20first%20%3D%20*head_ref%3B%20%20%0A%20%20%20%20rest%20%20%3D%20first-%3Enext%3B%0A%20%0A%20%20%20%20%2F*%20List%20has%20only%20one%20node%20*%2F%0A%20%20%20%20if%20(rest%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20return%3B%20%20%20%0A%20%0A%20%20%20%20%2F*%20reverse%20the%20rest%20list%20and%20put%20the%20first%20element%20at%20the%20end%20*%2F%0A%20%20%20%20recursiveReverse(%26rest)%3B%0A%20%20%20%20first-%3Enext-%3Enext%20%20%3D%20first%3B%20%20%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20tricky%20step%20–%20see%20the%20diagram%20*%2F%0A%20%20%20%20first-%3Enext%20%20%3D%20NULL%3B%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%20%20%2F*%20fix%20the%20head%20pointer%20*%2F%0A%20%20%20%20*head_ref%20%3D%20rest%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%7D” message=”” highlight=”” provider=”manual”/]

Time Complexity: O(n)
Space Complexity: O(1)

[ad type=”banner”]

Python Programming:

[pastacode lang=”python” manual=”%23%20Simple%20and%20tail%20recursive%20Python%20program%20to%20%0A%23%20reverse%20a%20linked%20list%0A%20%0A%23%20Node%20class%20%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20initialize%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%0A%20%20%20%20def%20reverseUtil(self%2C%20curr%2C%20prev)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20last%20node%20mark%20it%20head%0A%20%20%20%20%20%20%20%20if%20curr.next%20is%20None%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20curr%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Update%20next%20to%20prev%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20curr.next%20%3D%20prev%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Save%20curr.next%20node%20for%20recursive%20call%0A%20%20%20%20%20%20%20%20next%20%3D%20curr.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20And%20update%20next%20%0A%20%20%20%20%20%20%20%20curr.next%20%3D%20prev%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20self.reverseUtil(next%2C%20curr)%20%0A%20%0A%20%0A%20%20%20%20%23%20This%20function%20mainly%20calls%20reverseUtil()%0A%20%20%20%20%23%20with%20previous%20as%20None%0A%20%20%20%20def%20reverse(self)%3A%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20self.reverseUtil(self.head%2C%20None)%0A%20%0A%20%0A%20%20%20%20%23%20Function%20to%20insert%20a%20new%20node%20at%20the%20beginning%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20%23%20Utility%20function%20to%20print%20the%20linked%20LinkedList%0A%20%20%20%20def%20printList(self)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while(temp)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%0A%20%0A%23%20Driver%20program%0Allist%20%3D%20LinkedList()%0Allist.push(8)%0Allist.push(7)%0Allist.push(6)%0Allist.push(5)%0Allist.push(4)%0Allist.push(3)%0Allist.push(2)%0Allist.push(1)%0A%20%0Aprint%20%22Given%20linked%20list%22%0Allist.printList()%0A%20%0Allist.reverse()%0A%20%0Aprint%20%22%5CnReverse%20linked%20list%22%0Allist.printList()%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

Given linked list
1 2 3 4 5 6 7 8

Reversed linked list
8 7 6 5 4 3 2 1