首页 > 代码库 > Reverse Linked List II leetcode

Reverse Linked List II leetcode

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->3->4->5->NULLm = 2 and n = 4, 得到 1->4->3->2->5->NULL.

1、首先先定位到开始逆置的上一个节点,如上  m=2   那么  节点1就为 上一个开始逆置的节点,因为有可能出现m=1的情况,所以我们需要定义一个头节点

2、找到开始逆置的上一个节点p之后,就开始逆置了,逆置的个数为   n-m+1,注意需要保存开始逆置的第一个节点,因为逆置完成之后需要将该节点指向最后一个节点(n指向)的下一个节点

代码如下:

<span style="font-size:18px;">/**
 * 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) {
        
        ListNode *p,*q;
        ListNode *result=new ListNode(0);
        result->next=head;
        p=result;
        if(m==n)
            return head;
        
        int temp=n-m;
        while(m>1)
        {
          p=p->next;
          --m;
        }
       
        //这时p已经指向了开始逆置的上一个节点
        //用temp记录需要将几个节点逆置
        
        ListNode *start,*end;
        start=p->next;
        end=start;  //用end保存开始逆置的第一个节点,该节点在逆置结束后需要指向最后一个逆置节点的下一个节点
        while(temp>=0) //开始逆置
        {
            q=start;
            start=start->next;
            q->next=p->next;
            p->next=q;
            --temp;
            
        }
        end->next=start; //end指向逆置后的下一个节点
       
            return result->next;
       
        
    }
};</span>


Reverse Linked List II leetcode