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

思路：

1.(头二个节点已经事先处理)找出要换位置的两个节点的前驱节点，设为tempHead，设要更换的两个节点为p,q

2.那么直接p节点拿出，tempHead->next=q;p->next=NULL;

3.然后就是普通把p几点插入到q节点后面即可。p->next=q->next;q->next=p;

4.最后把暂时头部节点后移两个位置，进行下一次更换。

图解如下：

代码：

class Solution {

public:

    ListNode* swapPairs(ListNode* head) {

        ListNode* res;

        if(head==NULL) return NULL;

        if(head->next==NULL) return head;

        //交换第一,二个节点

        ListNode* first=head->next;

        head->next=first->next;

        first->next=head;

        ListNode* tempHead=first->next;

        ListNode* p;

        ListNode* q;

        while (tempHead)

        {

            if(tempHead->next!=NULL&&tempHead->next->next!=NULL){

                p=tempHead->next;

                q=tempHead->next->next;

            }

            else return first;

            tempHead->next=q;

            p->next=NULL;//中间节点插入即可

            p->next=q->next;

            q->next=p;

            tempHead=q->next;

        }

        return first;

    }

};

巴特西

Swap Nodes in Pairs（链表操作）

最新文章

热门文章