【python】Leetcode每日一题-反转链表 II

【python】Leetcode每日一题-反转链表 II

【题目描述】

给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

【分析】

既然有进阶提示，那就直接开始进阶解法吧！??

• 思路：

  • 创建一个新链表头空节点，遍历时，当 index < left 时，直接使用原链表节点，当 \(left\leq index \leq right\) 时，利用临时节点将中间部分指针方向反转，再让前一部分指向中间部分头结点，中间部分尾节点指向后一部分。

  • 时间复杂度：\(O(m)\)

  • 

  AC代码：

  # Definition for singly-linked list.
  class ListNode(object):
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  class Solution(object):
      def reverseBetween(self, head, left, right):
          """
          :type head: ListNode
          :type left: int
          :type right: int
          :rtype: ListNode
          """
          newList = ListNode()
          index = 1
          p = newList
  
          while(head):
          	if(index==left):
          		break
          	p.next = head
          	head = head.next
          	p = p.next
          	index += 1
          
          t = head
          
          q = head
          head = head.next
         	while(index < right):
         		t_ = q
         		q = head
         		head = head.next
         		q.next = t_
         		index += 1
  
         	p.next = q
         	if head == None:
  	       	t.next = None
         	else:
         		t.next = head
         	
         	return newList.next
  

• 结果：

  

• 讨论：

  • 官方题解： 戳这里
  • 官方解法中的头插法和自己的优化版的穿针引线的时间复杂度相同，但提供了一个很好的思路。