leetcode 24 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

---

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        dump = ListNode(-1)
        dump.next = head
        prev = dump
        cur = head
        while cur:
            tail = cur.next
            if not tail:
                break
            cur.next = tail.next
            tail.next = cur
            prev.next = tail
            prev = cur
            cur = cur.next
        return dump.next

• 递归

  class Solution {
      public ListNode swapPairs(ListNode head) {
          if(head == null || head.next == null){
              return head;
          }
          ListNode next = head.next;
          head.next = swapPairs(next.next);
          next.next = head;
          return next;
      }
  }

• 非递归

  class Solution {
      public ListNode swapPairs(ListNode head) {
          ListNode pre = new ListNode(0);
          pre.next = head;
          ListNode temp = pre;
          while(temp.next != null && temp.next.next != null) {
              ListNode start = temp.next;
              ListNode end = temp.next.next;
              temp.next = end;
              start.next = end.next;
              end.next = start;
              temp = start;
          }
          return pre.next;
      }
  }