本文共 3470 字，大约阅读时间需要 11 分钟。

 leetcode 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->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Python代码（将q,p,end,pPre,pNext等变量定义成 函数内的局部变量）：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def reverseBetween(self, head, m, n):        """        :type head: ListNode        :type m: int        :type n: int        :rtype: ListNode        """        if m==n:            return head        q=None # q用来指向第m个节点的前驱，初始值设为None        p=head # p用来指向当前节点，初始指向头节点        # 通过下面的for循环，将p指向第m个节点，q指向其前驱        for i in range(1,m):            q=p            p=p.next                end=p    #在将p后移之前，执行此语句，记录第m个节点的地址        pPre=p   #在将p后移之前，执行此语句，pPre用来指向p的前驱，初始时，pPre指向第m个节点。        p=p.next #将p后移一步，使p指向第m+1个节点        pNext=None #pNext用来指向节点p的后驱，具体的赋值操作在下面的for循环内进行。        # 通过下面的for循环，翻转链表指定部分        for i in range(m+1,n+1):            pNext=p.next            p.next=pPre            pPre=p            p=pNext                end.next=p        if q==None:            head=pPre        else:            q.next=pPre        return head

Python代码（将q,p,end,pPre,pNext等变量定义成 类的实例的数据成员）：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def reverseBetween(self, head, m, n):        """        :type head: ListNode        :type m: int        :type n: int        :rtype: ListNode        """        if m==n:            return head        self.q=None # q用来指向第m个节点的前驱，初始值设为None        self.p=head # p用来指向当前节点，初始指向头节点        # 通过下面的for循环，将p指向第m个节点，q指向其前驱        for i in range(1,m):            self.q=self.p            self.p=self.p.next                self.end=self.p    #在将p后移之前，执行此语句，记录第m个节点的地址        self.pPre=self.p   #在将p后移之前，执行此语句，pPre用来指向p的前驱，初始时，pPre指向第m个节点。        self.p=self.p.next #将p后移一步，使p指向第m+1个节点        self.pNext=None #pNext用来指向节点p的后驱，具体的赋值操作在下面的for循环内进行。        # 通过下面的for循环，翻转链表指定部分        for i in range(m+1,n+1):            self.pNext=self.p.next            self.p.next=self.pPre            self.pPre=self.p            self.p=self.pNext                self.end.next=self.p        if self.q==None:            head=self.pPre        else:            self.q.next=self.pPre        return head

C++代码：

/** * 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(m==n)return head;        ListNode *q=NULL; //指针变量q用来指向第m个节点的前驱，初始值设为NULL        ListNode *p=head; //指针变量p用来指向当前节点，初始指向头节点        //通过下面的for循环，将p指向第m个节点，q指向其前驱        for(int i=1;i
   
    next;        }        ListNode *end=p;  //在将指针p后移之前，执行此语句，记录第m个节点的地址        ListNode *pPre=p;//在将指针p后移之前，执行此语句，使pPre指向p的前驱，初始时，pPre指向第m个节点。        p=p->next;       //将指针p后移一步，使p指向第m+1个节点        ListNode *pNext=NULL;//指针变量pNext用来指向节点p的后驱，具体的赋值操作在下面的for循环内进行。        //通过下面的for循环，翻转链表指定部分        for(int i=m+1;i<=n;i++)        {            pNext=p->next;            p->next=pPre;            pPre=p;            p=pNext;        }        end->next=p;        if(q!=NULL)q->next=pPre;        else head=pPre;        return head;    }};
   

转载地址：http://edyai.baihongyu.com/