Jamzen的技术博客
0%

LeetCode.反转链表

发表于 分类于 Valine：

反转一个单链表。

  • 示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
  • 进阶:
    你可以迭代或递归地反转链表

解法：

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
42
43
44
object ReverseLinkedList {
     def main(args: Array[String]): Unit = {
          println(reverse(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, null)))))))
          println(reverse2(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, null)))))))
     }

     /**
      * 递归
      */
     def reverse(node: ListNode): ListNode = {
          if (node == null || node.next == null) {
               node
          } else {
               val newNode = reverse(node.next)
               node.next.next = node
               node.next = null
               newNode
          }
     }

     /**
      * 迭代
      */
     def reverse2(node: ListNode): ListNode = {
          if(node == null || node.next == null){
               return node
          }
          var pre = node
          var cur = node.next
          var tmp = node.next
          while (cur != null) {
               tmp = cur.next
               cur.next = pre
               pre = cur
               cur = tmp
          }
          node.next = null
          pre
     }

     case class ListNode(value: Int, var next: ListNode)

}