{"id":27293,"date":"2018-01-20T20:46:48","date_gmt":"2018-01-20T15:16:48","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27293"},"modified":"2018-01-20T20:46:48","modified_gmt":"2018-01-20T15:16:48","slug":"java-algorithm-write-function-reverse-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-write-function-reverse-linked-list\/","title":{"rendered":"Java Algorithm &#8211; Write a function to reverse a linked list"},"content":{"rendered":"<p>Given pointer to the head node of a linked list, the task is to reverse the linked list.<\/p>\n<p><strong>Examples<\/strong>:<\/p>\n<pre>Input : Head of following linked list  \r\n       1->2->3->4->NULL\r\nOutput : Linked list should be changed to,\r\n       4->3->2->1->NULL\r\n\r\nInput : Head of following linked list  \r\n       1->2->3->4->5->NULL\r\nOutput : Linked list should be changed to,\r\n       5->4->3->2->1->NULL\r\n\r\nInput : NULL\r\nOutput : NULL\r\n\r\nInput  : 1->NULL\r\nOutput : 1->NULL<\/pre>\n<div id=\"practice\">\n[ad type=\u201dbanner\u201d]\n<p><strong>Iterative Method<\/strong><br \/>\nIterate trough the linked list. In loop, change next to prev, prev to current and current to next<\/p>\n<p><strong>Java Programming:<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<pre>Given linked list\r\n85 15 4 20 \r\nReversed Linked list \r\n20 4 15 85<\/pre>\n<p><strong>Time Complexity:<\/strong> O(n)<br \/>\n<strong>Space Complexity:<\/strong> O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Recursive Method:<\/strong><\/p>\n<pre>   1) Divide the list in two parts - first node and rest of the linked list.\r\n   2) Call reverse for the rest of the linked list.\r\n   3) Link rest to first.\r\n   4) Fix head pointer<\/pre>\n<\/div>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27280\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linked-List-Rverse.png\" alt=\"Write a function to reverse a linked list\" width=\"400\" height=\"420\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linked-List-Rverse.png 400w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linked-List-Rverse-286x300.png 286w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><\/p>\n<p><strong>C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dvoid%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\u2013%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity:<\/strong> O(n)<br \/>\n<strong>Space Complexity:<\/strong> O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Java Programming:<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20for%20reversing%20the%20Linked%20list%0A%20%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%3B%0A%20%0A%20%20%20%20static%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20simple%20and%20tail%20recursive%20function%20to%20reverse%0A%20%20%20%20%2F%2F%20a%20linked%20list.%20%20prev%20is%20passed%20as%20NULL%20initially.%0A%20%20%20%20Node%20reverseUtil(Node%20curr%2C%20Node%20prev)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20last%20node%20mark%20it%20head*%2F%0A%20%20%20%20%20%20%20%20if%20(curr.next%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20curr%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20Update%20next%20to%20prev%20node%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20curr.next%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Save%20curr-%3Enext%20node%20for%20recursive%20call%20*%2F%0A%20%20%20%20%20%20%20%20Node%20next1%20%3D%20curr.next%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20and%20update%20next%20..*%2F%0A%20%20%20%20%20%20%20%20curr.next%20%3D%20prev%3B%0A%20%0A%20%20%20%20%20%20%20%20reverseUtil(next1%2C%20curr)%3B%0A%20%20%20%20%20%20%20%20return%20head%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20prints%20content%20of%20double%20linked%20list%0A%20%20%20%20void%20printList(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20list.head%20%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20%20list.head.next%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next%20%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next%20%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next.next%20%3D%20new%20Node(6)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next.next.next%20%3D%20new%20Node(7)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next.next.next.next%20%3D%20new%20Node(8)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Original%20Linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%20%20%20%20%20%20%20Node%20res%20%3D%20list.reverseUtil(head%2C%20null)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Reversed%20linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(res)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%20%0A%2F%2F%20This%20code%20has%20been%20contributed%20by%20Mayank%20Jaiswal\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>Given linked list\r\n1 2 3 4 5 6 7 8\r\n\r\nReversed linked list\r\n8 7 6 5 4 3 2 1<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Java Algorithm &#8211; Write a function to reverse a linked list &#8211; Linked List &#8211; Given pointer to the head node of a linked list, the task is to reverse<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,2139,79476,79478],"tags":[80299,81347,81346,81349,80298,80296,81345,80300,81342,81348,80297,81344,81343],"class_list":["post-27293","post","type-post","status-publish","format-standard","hentry","category-coding","category-java","category-linked-list","category-singly-linked-list","tag-algorithm-to-reverse-a-linked-list-in-data-structure","tag-how-to-reverse-a-linked-list-c","tag-how-to-reverse-a-linked-list-in-c","tag-how-to-reverse-a-linked-list-python","tag-reverse-a-linked-list-algorithm","tag-reverse-a-linked-list-c","tag-reverse-a-linked-list-in-groups-of-size-k","tag-reverse-a-linked-list-recursively-c","tag-reverse-a-linked-list-using-recursion","tag-reverse-doubly-linked-list-java","tag-reverse-linked-list-recursive-java","tag-reversing-a-linked-list-in-c-with-explanation","tag-reversing-a-linked-list-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27293"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27293\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}