Created
May 17, 2021 03:13
-
-
Save adeydas/6d60eda7c0356f3e977c364d238ed827 to your computer and use it in GitHub Desktop.
Reverse LinkedList - Iterative
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for singly-linked list. | |
| * public class ListNode { | |
| * int val; | |
| * ListNode next; | |
| * ListNode() {} | |
| * ListNode(int val) { this.val = val; } | |
| * ListNode(int val, ListNode next) { this.val = val; this.next = next; } | |
| * } | |
| */ | |
| class Solution { | |
| /** | |
| Given list 1->2->3 | |
| Take 2 pointers: prev, curr | |
| prev - points to null, this is the initial state of the reversed list | |
| curr - points to head | |
| Now we need to point 1 -> null because our reversed list will be 3->2->1->null | |
| So we point curr.next to prev | |
| We also need to update curr to 2, so we point it to that | |
| And we need to update prev to 1, so we point it to curr | |
| Keep repeating that till the end of the list is reached | |
| **/ | |
| public ListNode reverseList(ListNode head) { | |
| ListNode prev = null; | |
| ListNode curr = head; | |
| while (curr != null) { | |
| // Keep the next element of curr becuase once we break the link, this element will be lost otherwise | |
| ListNode temp = curr.next; | |
| // from our example, flip the next of curr (1) to point to null resembling the reversed list | |
| curr.next = prev; | |
| // we need to prepare for doing the same for 2 and the node after 2 in the reversed list would 1, so change prev to 1 | |
| prev = curr; | |
| // next we will process 2, so move curr to 2 | |
| curr = temp; | |
| } | |
| // by the end of the list, curr would be null and the penultimate node would be prev, which would be the head of the list | |
| return prev; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment