Description

Given a linked list, swap every two adjacent nodes and return its head.Example:Given 1->2->3->4, you should return the list as 2->1->4->3.Note:Your algorithm should use only constant extra space.You may not modify the values in the list's nodes, only nodes itself may be changed.

Mind Path

Note1: Using only constant extra space means that we can't use recusive solutions. Note2: Not modifying the values means that we can only swap nodes to do the swap.

Solution

package com.dylan.leetcode;import java.util.List;import org.junit.Assert;import org.junit.Test;/** * Created by liufengquan on 2018/8/11. */public class SwapNodesInPairs {    public ListNode swapPairs(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode newHead = new ListNode(0);        ListNode temp = newHead;        temp.next = head;        while (head != null && head.next != null) {            temp.next = head.next;            ListNode next = head.next.next;            temp.next.next = head;            head = next;            temp = temp.next.next;            temp.next = head;        }        return newHead.next;    }    @Test    public void testSwapSwapPairs() {        ListNode listNode = init(1);        Assert.assertEquals(listNode, swapPairs(listNode));        ListNode second = init(2);        ListNode swapped = swapPairs(second);        Assert.assertEquals(1, swapped.val);        Assert.assertEquals(0, swapped.next.val);        ListNode third = init(3);        ListNode thirdSwap = swapPairs(third);        Assert.assertEquals(1, thirdSwap.val);        Assert.assertEquals(0, thirdSwap.next.val);        Assert.assertEquals(2, thirdSwap.next.next.val);    }    public ListNode init(int n) {        ListNode head = new ListNode(1);        ListNode temp = head;        for (int i = 0; i < n; i++) {            temp.next = new ListNode(i);            temp = temp.next;        }        return head.next;    }}