首页 > 代码库 > 【LeetCode】Reverse Linked List II

【LeetCode】Reverse Linked List II

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,

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

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

 

把[m,n]那一段抠出来,reverse之后,再拼回去。

主要就是考虑边界条件。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */struct Node{    ListNode* head;    ListNode* tail;    Node(ListNode* begin, ListNode* end): head(begin), tail(end) {}};class Solution {public:    ListNode *reverseBetween(ListNode *head, int m, int n) {        //find begin        ListNode* tail = head;        ListNode* cur = head;        ListNode* begin = NULL;        ListNode* end = NULL;        ListNode* pre = NULL;        int tmp = m;                while(--tmp)//--tmp        {            pre = cur;            cur = cur->next;        }        begin = cur;        tmp = n-m;        while(tmp--)//tmp--            cur = cur->next;        end = cur;                while(tail->next != NULL)            tail = tail->next;                //4 cases        if(begin == head)        {//result->head is head            if(end == tail)            {                //reverse all, return result->head                Node* result = reverse(begin, end);                result->tail->next = NULL;                return result->head;            }            else            {                //reverse from head to end, end->next=post, and return result->head                ListNode* post = end->next;                end->next = NULL;                Node* result = reverse(begin, end);                result->tail->next = post;                return result->head;            }        }        else        {//head is head           if(end == tail)            {                //reverse from begin to tail, pre->next = result->head, and return head                Node* result = reverse(begin, end);                pre->next = result->head;                result->tail->next = NULL;                return head;            }            else            {                //reverse from begin to end, pre->next = begin, end->next = post, and return head                ListNode* post = end->next;                end->next = NULL;                Node* result = reverse(begin, end);                pre->next = result->head;                result->tail->next = post;                return head;            }         }    }        Node* reverse(ListNode* begin, ListNode* end)    {        Node* result = new Node(begin, end);        if(begin == end)            return result;  //no change        else if(begin->next == end)        {            end->next = begin;            begin->next = NULL;            result->head = end;            result->tail = begin;            return result;        }        else        {            ListNode* pre = begin;            ListNode* cur = pre->next;            ListNode* post = cur->next;            while(post != NULL)            {                cur->next = pre;                pre = cur;                cur = post;                post = post->next;            }            cur->next = pre;            begin->next = NULL;            result->head = cur;            result->tail = begin;            return result;        }    }};

【LeetCode】Reverse Linked List II