题解 | 两两交换链表的节点

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC186 两两交换链表的节点
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode swapLinkedPair (ListNode head) {
        // return solution1(head);
        return solution2(head);
    }

    /**
     * 迭代
     * @param head
     * @return
     */
    private ListNode solution1(ListNode head){
        if(head==null || head.next==null){
            return head;
        }

        ListNode dummyHead = new ListNode(-1);
        ListNode odd,even,pre;
        pre = dummyHead;
        odd = head;
        while(odd!=null && odd.next!=null){
            even = odd.next;

            odd.next = even.next;
            even.next = odd;
            pre.next = even;
            pre = odd;
            odd = odd.next;
        }

        return dummyHead.next;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    private ListNode solution2(ListNode head){
        return swap(head);
    }

    /**
     * 交换: 递归
     * @param head
     * @return
     */
    private ListNode swap(ListNode head){
        if(head==null || head.next==null){
            return head;
        }

        ListNode odd,even;
        odd = head;
        even = head.next;

        odd.next = swap(even.next);
        even.next = odd;

        return even;
    }
}