题目

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.

分析

如演示样例所看到的。给定一个链表。要求交换链表中相邻两个节点。

对于此题的程序实现，必须注意的是指针的判空，否则。一不注意就会出现空指针异常。

AC代码

/**

 * Definition for singly-linked list.

 * 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   *p = head , *q = p->next;

        //首先交换头两个结点,同一时候保存q后结点

        ListNode *r = q->next;

        head = q;

        p->next = r;

        q->next = p;

        if (r && r->next)

        {

            ListNode *pre = p;

            p = p->next;

            q = p->next;

            while (q)

            {

                //保存q结点后结点

                ListNode *r = q->next;

                pre->next = q;

                p->next = r;

                q->next = p;

                if (r && r->next)

                {

                    pre = p;

                    p = r;

                    q = p->next;

                }

                else{

                    break;

                }

            }

        }

        return head;

    }

};

GitHub測试程序源代码