Question: https://oj.leetcode.com/problems/reverse-linked-list-ii/
Question Name: Reverse Linked List II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @param m, an integer # @param n, an integer # @return a ListNode def reverseBetween(self, head, m, n): # Actually, we do not need to reverse the nodes, when m == n. if m == n: return head # Add a pseudo head node, so that we can handle the case m == 1, # in a same way as that m. currentNode = pseoduHead = ListNode(-1) pseoduHead.next = head current = 0 # Find the last node before the to-reverse zone while current < m - 1: currentNode = currentNode.next current += 1 beforeReverseZone = currentNode # Push all the nodes in the reversing zone into one stack. stack = [] for _ in xrange(m, n+1): stack.append(currentNode.next) currentNode = currentNode.next # Find the first node after the to-reverse zone afterReverseZone = currentNode.next # Reverse the nodes in the stack. And record the begin and # end nodes. reverseListEnd = reverseListHead = stack.pop() while len(stack) != 0: reverseListEnd.next = stack.pop() reverseListEnd = reverseListEnd.next # Embed the reversed list into the original zone beforeReverseZone.next = reverseListHead reverseListEnd.next = afterReverseZone # Skip the pseudo head node return pseoduHead.next |