# LeetCode 24：Swap Nodes in Pairs

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.

（1）创建一个头节点，first不动，first.next作为交换后的头指针，最终返回；start指向每次循环交换两个节点中第一个节点

```ListNode first = new ListNode(0);
ListNode prev = first;
ListNode start = head;```

（2）start指针引用每次引用交换前两个节点中前面一个节点，记录下次的起点，所以每次交换的时候，先移到下两个节点起点

```start = head.next.next;
```

（3）交换位置，先将后面一个节点指向前面一个节点，后面断了也没关系，反正start已经记录了下一轮回

```head.next.next = head;
```

（4）将头节点换个位置，因为要交换位置，比如最终是0->2->1，因此更换prev.next的引用，同时也修改了first.next指向的位置，这才是最终要返回的

```prev.next = head.next;
```

（5）其实上面first.next已经指向了0->2->1，剩下的工作就是要恢复成（1）的指针的状态，也就是保持34和12时候一样；首先1作为34的头结点（因为1交换后在后方），就像0作为12的头结点一样，因此1指向3

```head.next = start;
```

（6）prev指向头结点，此时是1所在节点

```prev = head;
```

```head = head.next;
```

`package com.maoxiaomeng;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */class ListNode {     int val;    ListNode next;    ListNode(int x) {         val = x;     }}public class Solution {    public ListNode swapPairs(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode first = new ListNode(0);        first.next = head;        ListNode prev = first;        ListNode start = head;        while (head != null && head.next != null) {            start = head.next.next;            head.next.next = head;            prev.next = head.next;            head.next = start;            prev = head;            head = head.next;        }                return first.next;    }}`

Java源码

`package com.maoxiaomeng;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */class ListNode {     int val;    ListNode next;    ListNode(int x) {         val = x;     }}public class Solution {    public ListNode swapPairs(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode first = head.next;        head.next = swapPairs(first.next);        first.next = head;        return first;    }}`

OVER