首页 > 代码库 > 92. Reverse Linked List II

92. 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.

 

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* reverseBetween(ListNode* head, int m, int n) {12         if(!head){13             return head;14         }15         ListNode* newHead = new ListNode(-1);16         newHead->next = head;17         18         19         //因为m 可能为1,n为2,此时需要三个结点才能完成转换,20         //所以pNode设为newHead,21         //这样newHead结点,第一个,第二个结点就可以完成转换22         ListNode* pNode = newHead;23         24         for(int i = 1; i < m ; i++){25             pNode = pNode->next;26         }27         28         ListNode* pm = pNode->next;;29         30         for(int i = m ; i < n; i++){31             ListNode* n = pm->next;32             pm->next = n->next;33             n->next = pNode->next;34             pNode->next = n;35         }36         return newHead->next;37     }38 };

 

92. Reverse Linked List II