问题链接

Swap Nodes in Pairs | LeetCode OJ

问题描述

给出一个列表，交换每两个相邻的节点，然后返回头部。例如，给出列表1>2>3>4，返回的结果应该是2>1>4>3。你的算法必须使用固定的空间，并且不能修改节点的值。

解决办法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null){
            return head;
        }
        if (head.next == null) {
            return head;
        }
        head = swapPairs(null, head);
        ListNode copyHead = head;
        ListNode current = head;
        while (current.next != null && current.next.next != null) {
            current = swapPairs(current.next, current.next.next);
        }
        return copyHead;
    }

    public static ListNode swapPairs(ListNode previousHead, ListNode current) {
        ListNode next = current.next;
        ListNode restHead = null;
        if(next != null){
            restHead = next.next;
        }
        if (previousHead == null && next == null) {
            return current;
        } else if (previousHead == null && restHead == null) {
            next.next = current;
            current.next = null;
            return next;
        } else if (previousHead == null) {
            next.next = current;
            current.next = restHead;
            return next;
        } else if (next == null) {
            return current;
        } else if (restHead == null) {
            previousHead.next = next;
            next.next = current;
            current.next = null;
            return next;
        } else {
            previousHead.next = next;
            next.next = current;
            current.next = restHead;
            return next;
        }
    }
}