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
C Programming:
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20reverse%20the%20linked%20list%20*%2F%0Astatic%20void%20reverse(struct%20node**%20head_ref)%0A%7B%0A%20%20%20%20struct%20node*%20prev%20%20%20%3D%20NULL%3B%0A%20%20%20%20struct%20node*%20current%20%3D%20*head_ref%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%20%3D%20current-%3Enext%3B%20%20%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20prev%3B%20%20%20%0A%20%20%20%20%20%20%20%20prev%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%20%20%20*head_ref%20%3D%20prev%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20push%20a%20node%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%20%20%20while(temp%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%20%22%2C%20temp-%3Edata)%3B%20%20%20%20%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%20%20%0A%20%20%20%20%7D%0A%7D%20%20%20%20%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%20%20%0A%20%20%20%20%20push(%26head%2C%2020)%3B%0A%20%20%20%20%20push(%26head%2C%204)%3B%0A%20%20%20%20%20push(%26head%2C%2015)%3B%20%0A%20%20%20%20%20push(%26head%2C%2085)%3B%20%20%20%20%20%20%0A%20%20%20%20%20%0A%20%20%20%20%20printf(%22Given%20linked%20list%5Cn%22)%3B%0A%20%20%20%20%20printList(head)%3B%20%20%20%20%0A%20%20%20%20%20reverse(%26head)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20printf(%22%5CnReversed%20Linked%20list%20%5Cn%22)%3B%0A%20%20%20%20%20printList(head)%3B%20%20%20%20%0A%20%20%20%20%20getchar()%3B%0A%7D” 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)
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
C++ Programming:
[pastacode lang=”cpp” 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)
C++ Programming:
[pastacode lang=”cpp” manual=”%2F%2F%20A%20simple%20and%20tail%20recursive%20C%2B%2B%20program%20to%20reverse%0A%2F%2F%20a%20linked%20list%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%20%0Avoid%20reverseUtil(node%20*curr%2C%20node%20*prev%2C%20node%20**head)%3B%0A%20%0A%2F%2F%20This%20function%20mainly%20calls%20reverseUtil()%0A%2F%2F%20with%20prev%20as%20NULL%0Avoid%20reverse(node%20**head)%0A%7B%0A%20%20%20%20if%20(!head)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20reverseUtil(*head%2C%20NULL%2C%20head)%3B%0A%7D%0A%20%0A%2F%2F%20A%20simple%20and%20tail%20recursive%20function%20to%20reverse%0A%2F%2F%20a%20linked%20list.%20%20prev%20is%20passed%20as%20NULL%20initially.%0Avoid%20reverseUtil(node%20*curr%2C%20node%20*prev%2C%20node%20**head)%0A%7B%0A%20%20%20%20%2F*%20If%20last%20node%20mark%20it%20head*%2F%0A%20%20%20%20if%20(!curr-%3Enext)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20*head%20%3D%20curr%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Update%20next%20to%20prev%20node%20*%2F%0A%20%20%20%20%20%20%20%20curr-%3Enext%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Save%20curr-%3Enext%20node%20for%20recursive%20call%20*%2F%0A%20%20%20%20node%20*next%20%3D%20curr-%3Enext%3B%0A%20%0A%20%20%20%20%2F*%20and%20update%20next%20..*%2F%0A%20%20%20%20curr-%3Enext%20%3D%20prev%3B%0A%20%0A%20%20%20%20reverseUtil(next%2C%20curr%2C%20head)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20node%0Anode%20*newNode(int%20key)%0A%7B%0A%20%20%20%20node%20*temp%20%3D%20new%20node%3B%0A%20%20%20%20temp-%3Edata%20%3D%20key%3B%0A%20%20%20%20temp-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20linked%20list%0Avoid%20printlist(node%20*head)%0A%7B%0A%20%20%20%20while(head%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20head-%3Edata%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20cout%20%3C%3C%20endl%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20node%20*head1%20%3D%20newNode(1)%3B%0A%20%20%20%20head1-%3Enext%20%3D%20newNode(2)%3B%0A%20%20%20%20head1-%3Enext-%3Enext%20%3D%20newNode(3)%3B%0A%20%20%20%20head1-%3Enext-%3Enext-%3Enext%20%3D%20newNode(4)%3B%0A%20%20%20%20head1-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(5)%3B%0A%20%20%20%20head1-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(6)%3B%0A%20%20%20%20head1-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(7)%3B%0A%20%20%20%20head1-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(8)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Given%20linked%20list%5Cn%22%3B%0A%20%20%20%20printlist(head1)%3B%0A%20%20%20%20reverse(%26head1)%3B%0A%20%20%20%20cout%20%3C%3C%20%22%5CnReversed%20linked%20list%5Cn%22%3B%0A%20%20%20%20printlist(head1)%3B%0A%20%20%20%20return%200%3B%0A%7D” 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