Jamzen的技术博客
0%

LeetCode.两两交换链表中的节点

发表于 分类于 Valine：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

  • 示例一
    输入：head = [1,2,3,4]
    输出：[2,1,4,3]

解法一：一次遍历O(n)

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
45
46
47
48
49
50
51
object ReverseTwoNodeLinkedList {

    /**
    * 中间变量保存下次交换的节点O(n)
    */
     def main(args: Array[String]): Unit = {
          println(solution(
               ListNode(1, ListNode(2, null))
          ))

          println(solution(
               ListNode(1, ListNode(2, ListNode(3, ListNode(4, null))))
          ))

          println(solution(
               ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, null)))))
          ))
     }

     def solution(node: ListNode): ListNode = {
          if (node == null || node.next == null) {
               return node
          }
          val res = node.next
          var cur = res
          var head = node
          var tmp: ListNode = null
          while (cur != null) {
               tmp = cur.next
               cur.next = head
               if (tmp == null) {
                    head.next = tmp
                    cur = tmp
               } else {
                    if (tmp.next == null) {
                         head.next = tmp
                    } else {
                         head.next = tmp.next
                    }
                    head = tmp
                    cur = head.next
               }
          }

          res
     }

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

}