【python-leetcode92-翻转链表】反转链表2

发布时间：2020-12-20 09:54:31 所属栏目：Python 来源：网络整理

导读：问题描述：反转从位置 ? m ?到 ? n ?的链表。请使用一趟扫描完成反转。说明: 1 ≤? m ?≤? n ?≤ 链表长度。示例: 输入: 1-2-3-4-5-NULL, m = 2, n = 4输出: 1-4-3-2-5-NULL class ListNode: def __init__ (self,x): self.val = x self.next = Nonen1 =Li

问题描述：

反转从位置?m?到?n?的链表。请使用一趟扫描完成反转。

说明:
1 ≤?m?≤?n?≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL,m = 2,n = 4
输出: 1->4->3->2->5->NULL

class ListNode:
    def __init__(self,x):
        self.val=x
        self.next=None
n1=ListNode(1)
n2=ListNode(2)
n3=ListNode(3)
n4=ListNode(4)
n5=ListNode(5)
n1.next=n2;n2.next=n3;n3.next=n4;n4.next=n5

def printListNode(head):
    while head != None:
        print(head.val)
        head=head.next
#printListNode(n1)

 Solution:
     reverseBetween(self,head,m,n):
        if not head:
            return None
    
        cur,prev = head,None
        while m > 1:
            prev = cur
            cur = cur.next
            m,n = m - 1,n - 1

        p2,p1 = cur,prev

        while n:
            third = cur.next
            cur.next = prev
            prev = third
            n -= 1

        if p1:
            p1.next = prev
        else:
            head = prev
        p2.next = cur
         head
s=Solution()
s.reverseBetween(n1,2,4)
printListNode(n1)

具体过程：

初始状态：

进入第一个while循环之后：

之后定义两个链接指针,p1，p2

进入第二个while循环：

第一步：

第二步：

第三步：

此时退出循环。

然后p1.next指向prev，p2.next指向cur?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!