Leetcode: Reverse a singly linked list (8ms)

Reverse a singly linked list.

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

--------------------------------------------------

-------------------------------------------------

1. create a dummy node and connects to head

2. insert the following nodes after dummy node one by one

This way we don't need to go through the whole list in head to get the final node. The logic is simple and easy to follow:

////////////////////////////////////////////////////////////

class Solution {

public:

    ListNode* reverseList(ListNode* head) {

        //check input

        if(head==NULL || head->next==NULL)return head;

        ListNode *dummy= new ListNode(-1), *pre, *later;

        dummy->next=head;

        pre=head->next;

        later=pre->next;

        while(1){

            //insertion

            pre->next=dummy->next;

            dummy->next=pre;

            //check loop //NOTE: should check before updating points

            if(later==NULL)break;            

            //update pointers

            pre=later;

            later=pre->next;

        }

        head->next=NULL;//clear the tail

        return dummy->next;

    }

};