首页 > 代码库 > leetcode[92] Reverse Linked List II

leetcode[92] Reverse Linked List II

 

这题和Reverse Node in k-Group相关,主要是看如何翻转一个链表。这里是指定区间从第m个到第n个的翻转例如:

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

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

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *reverseBetween(ListNode *head, int m, int n)     {        if (!head || !(head -> next) || m == n) return head;        ListNode *pre = new ListNode(0);        pre -> next = head;        ListNode *mpre = pre;        ListNode *nnod = head;        while(m-- > 1 && n-- >0)        {            mpre = mpre -> next;            nnod = nnod -> next;        }        while(n-- > 0)            nnod = nnod -> next; // nnod最终是第n个node的下一个节点,用来判断反正的结束标志                ListNode *last = mpre -> next; // 反转相应部分链表        ListNode *cur = last -> next;        while(cur != nnod)        {            last -> next = cur -> next;            cur -> next = mpre -> next;            mpre -> next = cur;            cur = last -> next;        }        head = pre -> next;        delete pre;        return head;    }};

期间,我试过将nnod就表示第n个节点,然后用cur != nnode->next  来判断终止条件,发现是不行的。为什么呢,因为第n个node已经随着前面处理移到前面去了,所以还是一开始就找到第n个node的下一个作为结束的标志才好。

也可以如下:

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *reverseBetween(ListNode *head, int m, int n)     {        if (!head || !(head -> next) || m == n) return head;        ListNode *pre = new ListNode(0);        pre -> next = head;        ListNode *mpre = pre;        ListNode *nnext = head -> next;        while(m-- > 1 && n-- > 1)        {            mpre = mpre -> next;            nnext = nnext -> next;        }        while(n-- > 1)            nnext = nnext -> next;                ListNode *last = mpre -> next;        ListNode *cur = last -> next;        while(cur != nnext)        {            last -> next = cur -> next;            cur -> next = mpre -> next;            mpre -> next = cur;            cur = last -> next;        }        head = pre -> next;        delete pre;        return head;    }};
View Code

 

leetcode[92] Reverse Linked List II