leetcode 24. Swap Nodes in Pairs-蒲公英云

leetcode 24. Swap Nodes in Pairs

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.

这道题考察的是两个节点的交换，这里是指的是指针的交换，而不是值的交换，注意指针即可。

需要注意的地方是：设置head头结点，原因是要对第一队的交换做特殊处理，所以才添加一个head头节点。

代码如下：

/* class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }*/
/*
 * 设置head结点，两两交换
 * 
 * 设置head的原因是：考虑到第一对结点的交换，
 * 所以设置head结点，一遍统一处理
 * 
 * */
public class Solution 
{
     public ListNode swapPairs(ListNode head) 
     {
         if(head==null || head.next==null)
             return head;
         ListNode headListNode=new ListNode(-1);
         headListNode.next=head;
         ListNode fa=headListNode,now=fa.next,nextNow=now.next;
         while(now!=null && nextNow!=null)
         {
             now.next=nextNow.next;
             nextNow.next=now;
             fa.next=nextNow;
             fa=now;
             now=fa.next;
             nextNow=now!=null? now.next : null;
         }   
         return headListNode.next;
     }
}

下面是C++代码，就是指针交换即可，

代码如下：

#include <iostream>
using namespace std;
/*
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class Solution
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        ListNode* fa = newHead;
        ListNode* now = fa->next;
        ListNode* next = now->next;
        while (now != NULL && next != NULL)
        {
            ListNode* tmp = next->next;
            next->next = now;
            fa->next = next;
            now->next = tmp;
            fa = now;
            now = fa->next;
            next = now == NULL ? NULL : now->next;
        }
        return newHead->next;
    }
};