Skip to content

Latest commit

 

History

History
119 lines (83 loc) · 2.38 KB

206. Reverse Linked List.md

File metadata and controls

119 lines (83 loc) · 2.38 KB

206. Reverse Linked List

Difficulty : Easy

Question : Given the head of a singly linked list, reverse the list, and return the reversed list.

Example :

Input : head = [1,2,3,4,5]

Output : [5,4,3,2,1]

Solution :

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curr;
        ListNode*prev;
        prev=NULL;
        curr=head;
        while(curr!=NULL){
            ListNode* temp=curr->next;
            curr->next=prev;
            prev=curr;
            curr=temp;
        }
        return prev;
    }
};

Language - C++

Explanation -

Reversing a linked list is straightforward! We'll use two pointers, curr and prev, both of ListNode type. Initially, prev points to NULL and curr points to head.

Now, let's understand the process through an example:

Suppose the linked list is 2 -> 3 -> 5.

  • Initially:
    • curr is 2
    • prev is NULL

We begin a while loop where we'll make another pointer temp point to curr->next. Let’s walk through each iteration:

1st Iteration

  • Before the loop body:
    • curr = 2
    • prev = NULL
    • head = 2 -> 3 -> 5
  1. temp = curr->next:

    • temp now points to 3
  2. curr->next = prev:

    • The next pointer of curr (2) now points to NULL
    • Updated list: 2 -> NULL
  3. prev = curr:

    • prev now points to 2
  4. curr = temp:

    • curr now points to 3

2nd Iteration

  • Before the loop body:
    • curr = 3
    • prev = 2
    • head = 2 -> NULL
  1. temp = curr->next:

    • temp now points to 5
  2. curr->next = prev:

    • The next pointer of curr (3) now points to 2
    • Updated list: 3 -> 2 -> NULL
  3. prev = curr:

    • prev now points to 3
  4. curr = temp:

    • curr now points to 5

3rd Iteration

  • Before the loop body:
    • curr = 5
    • prev = 3
    • head = 2 -> NULL
  1. temp = curr->next:

    • temp now points to NULL
  2. curr->next = prev:

    • The next pointer of curr (5) now points to 3
    • Updated list: 5 -> 3 -> 2 -> NULL
  3. prev = curr:

    • prev now points to 5
  4. curr = temp:

    • curr now points to NULL

End of Loop

Now curr is NULL, so the while loop stops.

Result

The pointer prev now points to the reversed linked list: 5 -> 3 -> 2 -> NULL.


And there you have it! You've successfully reversed the linked list.