Reverse Singly LInked List

Very Simple -- but what to notice is that you have to think at least two steps!! Sometimes, if you just think one step, it is the special cases :)

class ListNode:
 def __init__(self,val):
  self.val = val
  self.next = None


def reverseLinkedList(head):
 if head == None or head.next == None:
  return head
 dummy = ListNode(0)
 dummy.next = head
 cur = head.next
 while cur != None:
  newcur = cur.next
  tstart = dummy.next
  dummy.next = cur
  cur.next = tstart
  head.next = newcur
  cur = newcur

 return dummy.next

## test block
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
a.next = b
b.next = c
c.next = d

x = reverseLinkedList(a)
while x is not None:
 print(x.val)
 x = x.next

This is the way that uses dummy head, but actually you dont really need the dummy, in this iterative function, the only nodes that needed to be tracked is the new head and the current node, which is the one to be added to the front, and until current is None, the traversal through the entire list is done, and the you return the current new head, and that's it!

def reverseLinkedList(head):
   if head == None or head.next == None:
       return head
   # last is the new head, and also is the real 'last' node of the current node, it has a meaning :)
   last = haed
   current = head.next
   while current is not None:
       head.next = current.next
       current.next = last
       last = current
       current = head.next
   return last 
       

The above code is also "in-place" reverse. maybe it would be a bit concise :)