Thursday, December 31, 2015

[Leetcode] Reverse Linked List

Problem 

Reverse a singly linked list.

Analysis


  • 这道题就是要把相邻两个node的指针指向反一反,反的过程当中要keep track of next node,不然这时候 node.next 变成前一个节点了
    • 所以我们采用两个指针,prev 和 curr 来记录相邻的两个节点
      • 反之前,先记录 curr.next, 即 tmp = curr.next 
      • 然后可以反了,curr.next = prev
      • 然后把prev 和 curr往右移,继续去处理还没反的nodes
        • prev = curr
        • curr = tmp
  • Time: O(n)
  • Space: O(1)

Code

No comments:

Post a Comment