转载

LeetCode反转链表II

LeetCode反转链表II

题目链接地址

  • 解题思路

    1->2->3->4->5->NULL

    分解成

    1->NULL 2->3->4->NULL 5->NULL

    然后对中间进行反转

    算法的复杂度很小,性能很号

    别看代码很长,其实很简单!

  • python代码

    
    # Definition for singly-linked list.
    
    
    # class ListNode(object):
    
    
    # def __init__(self, x):
    
    
    # self.val = x
    
    
    # self.next = None
    
    
    class Solution(object):
      def reverse(self, head):
          stack = []
          temp = head
          while temp != None:
              stack.append(temp)
              temp = temp.next
    
          start, end = None, None
    
          while len(stack) > 0:
              value = stack.pop()
              if end == None:
                  start, end = value, value
              else:
                  end.next = value
                  end = value
    
          end.next = None
          return start, end
    
      def reverseBetween(self, head, m, n):
          """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """
          if head == None or head.next == None:
              return head
    
          #找到关键element,一共四个
          temp, number = head, 0
    
          startOne, startTwo, endOne, endTwo = None, None, None, None
    
          while temp != None:
              number += 1
    
              if number == m-1:
                  startOne = temp
    
              if number == m:
                  startTwo = temp
    
              if number == n:
                  endOne = temp
    
              if number == n+1:
                  endTwo = temp
    
              temp = temp.next        
    
          endOne.next = None
    
          startTwo, endOne = self.reverse(startTwo)
    
          #print startOne.val, startTwo.val, endOne.val, endTwo.val
    
          if startOne != None: 
              startOne.next = startTwo
              endOne.next = endTwo
              return head
          else:
              endOne.next = endTwo
              return startTwo
正文到此结束
本文目录