{"id":2252,"date":"2020-07-29T07:34:45","date_gmt":"2020-07-29T07:34:45","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2252"},"modified":"2022-03-25T11:02:16","modified_gmt":"2022-03-25T11:02:16","slug":"reverse-link-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/reverse-link-list\/","title":{"rendered":"REVERSE LINK LIST"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Reversing a linked list,pointers<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Reverse a linked list from position M to N. Do it in-place and in one-pass.<\/p>\n

Example:<\/h4>\n
Given 1\u2212>2\u2212>3\u2212>4\u2212>5\u2212>NULL,\nM=1 and N=3,\nOutput:  3\u2212>2\u2212>1\u2212>4\u2212>5\u2212>NULL.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n<\/blockquote>\n
EXPLANATION:<\/h3>\n
\n
Since we have to reverse a part of the given linked list obviously we need the concept of reversing the linked list. We need to find the mth node and pass it to the reverse function (which will reverse the given part). But, before passing the mth node we need to traverse to the nth node and cut its link with (n+1)th node if present.<\/p>\n
Also we have to save the (m-1) node and also (n+1)th node address so that we can link the reversed part of the linked list again with the original linked list.<\/p>\n
There will be four variables.
\nPrev<\/code> \u2192 for storing the previous node, i.e. (m-1)th node.<\/p>\n
Start<\/code> \u2192 for storing the starting(mth) node of reversal.<\/p>\n
End<\/code> \u2192 for storing the ending node(nth) of reversal.<\/p>\n
Next<\/code> \u2192 for storing the next node, i.e. (n+1)th node.<\/p>\n
Now, we will pass Start to the reverse function and then will attach the reversed part with Start and End to get the reversed linked list.<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t