leetcode：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.

分析：题意为给予一个链表，交换相邻的两个节点然后返回头结点。要求算法空间复杂度为O(1).

思路：新建一个链表每次插入temp->next后再插入temp，注意要判断若最后只剩下一个节点则不需要交换，每次交换了节点要把尾节点的下一个指向空。

代码：

/**

 * 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 *helper=new ListNode(0);

        ListNode *temp=head;

        ListNode *cur=helper;

        while(temp  && temp->next)

        {

            ListNode *next=temp->next->next;

            cur->next=temp->next;

            cur=cur->next;

            cur->next=temp;

            cur=cur->next;

            cur->next=NULL;

            temp=next;

        }

        if(temp) cur->next=temp;

        return helper->next;

    }

};

巴特西

leetcode：Swap Nodes in Pairs

最新文章

热门文章