Swap Nodes in Pairs

题目

[24] Swap Nodes in Pairs  

https://leetcode.com/problems/swap-nodes-in-pairs/description/

* algorithms
* Medium (45.98%)
* Total Accepted:    352.7K
* Total Submissions: 762.9K
* Testcase Example:  '[1,2,3,4]'

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

 

Example:


Given 1->2->3->4, you should return the list as 2->1->4->3.

思路

这道题如果试图去用一大堆指针指向需要交换的节点以及之后的节点，然后迭代就会被弄晕。
最后还是试图使用递归的方法解决。

我们把这个问题分割称两个部分，其实就是首先交换先头两个节点，然后，去交换剩下来的链表。

我们让lists中，第一个节点为head，第二个节点为tail。

最终得到的结果无非就是tail->head->swap_pairs(tail.next)

解法

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
  return head if head == nil || head.next == nil
  tail = head.next
  left = tail.next
  tail.next = head
  head.next = swap_pairs(left)
  return tail
end

反思

变量太多把自己搞晕的时候，想想是否有简介的递归可以利用。