[leetcode题解]92.Reverse Linked List II(链表部分逆置)

leetcode第92题,reverse-linked-list-ii,题目是一个单链表的题目,给定一个单链表,然后告诉一个区间[n,m],然后要求将链表中第n到m个节点逆序,这里保证n和m是合法的,即1 <= n <= m <= 链表长度,链表的节点id从1开始计数。

思路比较简单,设定两个指针,以前以后,首先数n个节点,然后将后面的m – n个节点进行头插(逆序插入),最后把m后面的部分链接起来就可以了。由于是头插,所以,n到m的这段第一个节点就是逆置完后最后的那个节点,所以可以先把这个节点记录下来,最后完成的时候直接在后面链接上后面的节点即可。

c++代码:

class Solution {
//author:凌风技术站-iaccepted
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) 
    {
        ListNode *p = head, *pre = new ListNode(-1);
        pre->next = head;
        ListNode *q = pre;
        
        //先走过前m个元素,到达要倒序段的起始位置
        int idx = 1;
        while(idx < m)
        {
            p = p->next;
            q = q->next;
            ++idx;
        }
        
        //后面的m个元素将要倒序插入,所以插入完成之后,最后一个元素就是现在的
        //第一个元素p,这里先记录下来,后面方便链接。
        ListNode *tail = p, *t = NULL;
        q->next = NULL;
        while(idx <= n)
        {
            t = p->next;
            p->next = q->next;
            q->next = p;
            p = t;
            ++idx;
        }
        
        //最后将链表连接上倒序段后面剩下的一部分就完成了
        tail->next = p;
        return pre->next;
    }
};

python:

class Solution(object):

    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        :author:凌风技术站-iaccepted
        """
        idx = 1
        pre = ListNode(-1)
        pre.next = head

        p, q = head, pre
        while idx < m:
            p = p.next
            q = q.next
            idx += 1
        q.next = None
        tail = p
        while idx <= n:
            t = p.next
            p.next = q.next
            q.next = p
            p = t
            idx += 1
        tail.next = p
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]92.Reverse Linked List II(链表部分逆置)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/79.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注