Problem: http://www.lintcode.com/en/problem/reverse-linked-list/
Reverse a linked list.
In [1]:
class Node:
def __init__(self, value=None, next=None):
self._value = value
self._next = next
@property
def value(self):
return self._value
@property
def next(self):
return self._next
@next.setter
def next(self, next=None):
self._next = next
# 8765 -> 5678
a0 = Node(8)
a1 = Node(7)
a2 = Node(6)
a3 = Node(5)
a0.next = a1
a1.next = a2
a2.next = a3
def reverse_linkedlist(l0):
if l0 is None or l0.next is None:
return l0
head = l0
newhead = None
nextnode=None
while head:
nextnode = head.next
head.next = newhead
newhead = head
head = nextnode
return newhead
r0 = reverse_linkedlist(a0)
while (r0):
print(r0.value)
r0 = r0.next
Problem: http://www.lintcode.com/en/problem/reverse-linked-list-ii/
Reverse a linked list from position m to n.
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
In [10]:
class Node:
def __init__(self, value=None, next=None):
self._value = value
self._next = next
@property
def value(self):
return self._value
@property
def next(self):
return self._next
@next.setter
def next(self, next=None):
self._next = next
# 87654321, m=3, n=6 -> 87345621
a0 = Node(8)
a1 = Node(7)
a2 = Node(6)
a3 = Node(5)
a4 = Node(4)
a5 = Node(3)
a6 = Node(2)
a7 = Node(1)
a0.next = a1
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5
a5.next = a6
a6.next = a7
def reverseBetween(head, m, n):
if head is None or m == n:
return head
first = head
c = 0
prev = None
while (head and c < m-1):
#for c in range(m):
prev = head
head = head.next
c += 1
new_head = prev
new_tail = head
while (head and c <= n-1):
next_node = head.next
head.next = new_head
new_head = head
head = next_node
c += 1
new_tail.next = next_node
if not prev is None:
prev.next = new_head
else:
first = new_head
return first
n = reverseBetween(a0, 1, 6)
while (n):
print(n.value)
n = n.next
In [ ]: