Question:

Given a linked list, swap every two adjacent nodes and return its head.

For example,

Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 

Analysis:

给出一个链表，交换两个彼此相邻的节点。注意：不能只是交换节点的数据，而是要真正的交换节点。只能使用固定的额外空间。

这道题目就是考察链表指针间的操作。为了与后面的保持一致，这里在head结点前面加一个首节点，让它指向head。除了交换两个交换加点间的指针，还要考虑该两个结点的前一个、后一个结点的连接性，因此需要一个额外的指针，指向交换节点的前一个节点。同时保证链表的链首不要丢失。

 

Answer：

/** * 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 || head.next == null) //若链表为空或只有一个节点，则返回原链表即可            return head;                ListNode hh = new ListNode(-1);        hh.next = head; //为链表加一个头结点                ListNode p = hh, i = p.next, j = i.next;        while(i != null || j != null) { //偶数个结点时i，j为空，奇数个节点时j为空            p.next = j;            i.next = j.next;            j.next = i;            p = i;            if(p.next == null)                return hh.next;            if(p.next.next == null)                return hh.next;            i = p.next;            j = i.next;        }                return hh.next;            }}