{"id":2257,"date":"2023-07-04T15:11:55","date_gmt":"2023-07-04T09:41:55","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2257"},"modified":"2023-07-04T15:14:05","modified_gmt":"2023-07-04T09:44:05","slug":"reverse-a-linked-list","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/reverse-a-linked-list\/","title":{"rendered":"Reverse a Linked List"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#recursive-approach\">Recursive Approach<\/a><\/li><li><a href=\"#implementation-of-recursive-approach\">Implementation Of Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#iterative-approach\">Iterative Approach<\/a><\/li><li><a href=\"#dry-run-of-the-iterative-approach\">Dry Run of the Iterative Approach<\/a><\/li><li><a href=\"#implementation-of-iterative-approach\">Implementation of Iterative Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#reverse-a-linked-list-in-c\">Reverse A Linked List In C++<\/a><\/li><li><a href=\"#-reverse-a-linked-list-in-java\"><meta charset=\"utf-8\">Reverse A Linked List In Java<\/a><\/li><li><a href=\"#reverse-a-linked-list-in-python\">Reverse A Linked List In Python<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-time-complexity-of-reversing-a-linked-list\">Q.1: What is the time complexity of reversing a linked list?<\/a><\/li><li><a href=\"#q2-can-we-use-stack-to-reverse-the-linked-list\">Q.2: Can we use Stack to reverse the Linked List?<\/a><\/li><li><a href=\"#q3-will-the-above-approaches-change-the-address-of-the-node\">Q.3: Will the above approaches change the address of the node?<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to switch the list by changing the links between nodes.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input:<\/strong> [1,2,3,4,5,NULL]<\/li><li><strong>Output:<\/strong> [5,4,3,2,1,NULL]<\/li><li><strong>Explanation:<\/strong><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Linked List Example\"  class=\"wp-image-2263 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-300x146.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-768x375.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-380x186.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-550x269.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-800x391.jpg 800w\" ><figcaption>Example<\/figcaption><\/figure>\n\n\n\n<ul><li><strong>Input:<\/strong> [3,4,5]<\/li><li><strong>Output:<\/strong> [5,4,3]<\/li><li><strong>Explanation:<\/strong><\/li><\/ul>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Example 2\"  class=\"wp-image-2262 pk-lazyload\"  width=\"518\"  height=\"426\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 518px) 100vw, 518px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3.jpg 616w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-300x247.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-380x313.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-550x453.jpg 550w\" ><\/figure><\/div>\n\n\n\n<h2 id=\"recursive-approach\">Recursive Approach<\/h2>\n\n\n\n<p>The recursive approach to reverse a linked list is simple, we have to divide the linked lists into two parts and i.e. first node and the rest of the linked list, and then call the recursion for the other part by maintaining the connection.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Recursive Approach\"  class=\"wp-image-2261 pk-lazyload\"  width=\"610\"  height=\"719\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 610px) 100vw, 610px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-867x1024.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-867x1024.jpg 867w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-254x300.jpg 254w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-380x449.jpg 380w\" ><figcaption>Recursive Approach<\/figcaption><\/figure><\/div>\n\n\n\n<h2 id=\"implementation-of-recursive-approach\">Implementation Of Recursive Approach<\/h2>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">ListNode* reverseList(ListNode* head) {\n    if(!head || !(head->next))  return head;\n    auto res = reverseList(head->next);\n    head->next->next = head;\n    head->next = NULL;\n    return res;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static class Node {\n  int data;\n  Node next;\n  Node(int d) {\n    data = d;\n    next = null;\n  }\n}\n\nstatic Node reverse(Node head) {\n  if (head == null || head.next == null)\n    return head;\n\n  Node rest = reverse(head.next);\n  head.next.next = head;\n\n  head.next = null;\n  return rest;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">  def reverse(self, head):\n \n        # If head is empty or has reached the list end\n        if head is None or head.next is None:\n            return head\n \n        # Reverse the rest list\n        rest = self.reverse(head.next)\n \n        # Put first element at the end\n        head.next.next = head\n        head.next = None\n \n        # Fix the header pointer\n        return rest<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(N), Where N is the size of the linked list.<\/li><li><strong>Space complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"iterative-approach\">Iterative Approach<\/h2>\n\n\n\n<ul><li>We will use 3 variables: prevNode, head, and nextNode.<\/li><li>prevNode to NULL<\/li><li>nextNode can stay empty;<\/li><li>Then we will continue our loop until our current maidenhead pointer is truthy (ie: not NULL), which implies that we reached the end of the linked list<\/li><li>During our loop, we first of all update nextNode so that it acquires its namesake value, as head-&gt;next.<\/li><li>Finally, we update the head with the value we stored in nextNode.<\/li><li>And finally, we go on with the loop until we can. After the loop, we return prevNode.<\/li><\/ul>\n\n\n\n<h2 id=\"dry-run-of-the-iterative-approach\">Dry Run of the Iterative Approach<\/h2>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dru Run of Iterative Approach\"  class=\"wp-image-2260 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-300x146.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-768x375.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-380x186.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-550x269.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-800x391.jpg 800w\" ><figcaption>Dru Run of Iterative Approach<\/figcaption><\/figure><\/div>\n\n\n\n<h2 id=\"implementation-of-iterative-approach\">Implementation of Iterative Approach<\/h2>\n\n\n\n<h3 id=\"reverse-a-linked-list-in-c\">Reverse A Linked List In C++<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">ListNode* reverseList(ListNode* head) {\n        ListNode *prev = NULL, *cur=head, *tmp;\n        while(cur){\n            tmp = cur->next;\n            cur->next = prev;\n            prev = cur;\n            cur = tmp;\n        }\n        return prev;\n   }<\/pre>\n\n\n\n<h3 id=\"-reverse-a-linked-list-in-java\"><span id=\"reverse-a-linked-list-in-java\"><meta charset=\"utf-8\">Reverse A Linked List In Java<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static class Node {\n\n  int data;\n  Node next;\n\n  Node(int d) {\n    data = d;\n    next = null;\n  }\n}\n\n\/* Function to reverse the linked list *\/\nNode reverse(Node node) {\n  Node prev = null;\n  Node current = node;\n  Node next = null;\n  while (current != null) {\n    next = current.next;\n    current.next = prev;\n    prev = current;\n    current = next;\n  }\n  node = prev;\n  return node;\n}<\/pre>\n\n\n\n<h3 id=\"reverse-a-linked-list-in-python\">Reverse A Linked List In Python<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverse(self):\n  prev = None\ncurrent = self.head\nwhile (current is not None):\n  next = current.next\ncurrent.next = prev\nprev = current\ncurrent = next\nself.head = prev<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(N), Where N is the size of the array.<\/li><li><strong>Space complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/reverse-linked-list\/\" target=\"_blank\">Reverse a Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/reverse-link-list-ii\/\" target=\"_blank\">Reverse Linked List II<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-time-complexity-of-reversing-a-linked-list\"><span id=\"q-1-what-is-the-time-complexity-of-reversing-a-linked-list\">Q.1: What is the time complexity of reversing a linked list?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>It is linear in time i.e. O(n) where n is the size of the linked list.<\/p>\n\n\n\n<h3 id=\"q2-can-we-use-stack-to-reverse-the-linked-list\"><span id=\"q-2-can-we-use-stack-to-reverse-the-linked-list\">Q.2: Can we use Stack to reverse the Linked List?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, but the space complexity will increase to O(N).<\/p>\n\n\n\n<h3 id=\"q3-will-the-above-approaches-change-the-address-of-the-node\"><span id=\"q-3-will-the-above-approaches-change-the-address-of-the-node\">Q.3: Will the above approaches change the address of the node?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>No, we should try not to change the address of the node.<\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/\" target=\"_blank\">Detect Loop in Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/add-two-numbers-represented-by-linked-lists\/\" target=\"_blank\">Add Two Numbers Represented by Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/delete-node-in-a-linked-list\/\" target=\"_blank\">Delete Node in a Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/intersection-of-two-linked-lists\/\" target=\"_blank\">Intersection of Two Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-interview-questions\/\" target=\"_blank\">Linked List Interview Questions<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-mcq\/\" target=\"_blank\">Linked List MCQ<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/application-of-linked-list\/\" target=\"_blank\">Application of Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/types-of-linked-list\/\" target=\"_blank\">Types of Linked List<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a pointer to the head node of a linked list, the task is to reverse&hellip;\n","protected":false},"author":5,"featured_media":2259,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[392],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2257"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2257"}],"version-history":[{"count":7,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2257\/revisions"}],"predecessor-version":[{"id":21132,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2257\/revisions\/21132"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2259"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}