链表问题——两两交换链表中的关于swap(p,q)的无效性讨论【相邻节点】

来杯Sherry

发布于 2023-07-24 19:21:26

1590

发布于 2023-07-24 19:21:26

文章被收录于专栏：第一专栏第一专栏

两两交换链表中的节点

问题描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入说明

首先输入链表长度len，然后输入len个整数，以空格分隔。

输出说明

输出格式见范例

输入范例

4 1 2 3 4

输出范例

head–>2–>1–>4–>3–>tail

题解

完整代码

问题不难，完整代码及注释如下：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;



struct ListNode

{

    int val;

    ListNode *next;

    ListNode() : val(0), next(NULL) {}

    ListNode(int x) : val(x), next(NULL) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}

};

class Solution
{

public:

    ListNode* swapPairs(ListNode* head)
    {

        //填充本函数完成功能
        ListNode* p=head,*q,*fade_head;
        fade_head = new ListNode;
        fade_head ->next =head;
        ListNode *mark = fade_head;//direct to swap(p,q) 的前节点

        //len
        int len =0;
        while(p)
        {
            len++;
            p=p->next;
        }


        if(len >1)
        {
            //deal
            p=head;
            int tot=0;
            while(p)
            {
                tot++;
                if(tot == 2)//swap(p,q), 保证了q的存在
                {
                    //swap(p,q)
                    mark->next =p;
                    q->next = p->next;
                    p->next = q;

                    //init
                    mark = q;
                    tot=0;
                    q=p;//前面 p、q节点换位置了
                    p=q->next;

                }
                //
                q=p;
                p=p->next;
            }
        }
        head =fade_head->next;
        return head;

    }

};

ListNode *createByTail()

{

    ListNode *head;

    ListNode *p1,*p2;

    int n=0,num;

    int len;

    cin>>len;

    head=NULL;

    while(n<len && cin>>num)

    {

        p1=new ListNode(num);

        n=n+1;

        if(n==1)

            head=p1;

        else

            p2->next=p1;

        p2=p1;

    }

    return head;

}

void  displayLink(ListNode *head)

{

    ListNode *p;

    p=head;

    cout<<"head-->";

    while(p!= NULL)

    {

        cout<<p->val<<"-->";

        p=p->next;

    }

    cout<<"tail\n";

}

int main()

{

    ListNode* head = createByTail();

    head=Solution().swapPairs(head);

    displayLink(head);

    return 0;

}

关于swap(p,q)的无效性讨论

p 、 q 为相邻节点

swap()的思想出现在下面函数中，

class Solution
{

public:

    ListNode* swapPairs(ListNode* head)
    {

        //填充本函数完成功能
        ListNode* p=head,*q,*fade_head;
        fade_head = new ListNode;
        fade_head ->next =head;
        ListNode *mark = fade_head;//direct to swap(p,q) 的前节点

        //len
        int len =0;
        while(p)
        {
            len++;
            p=p->next;
        }


        if(len >1)
        {
            //deal
            p=head;
            int tot=0;
            while(p)
            {
                tot++;
                if(tot == 2)//swap(p,q), 保证了q的存在
                {
                    //swap(p,q)
                    mark->next =p;
                    q->next = p->next;
                    p->next = q;

                    //init
                    mark = q;
                    tot=0;
                    q=p;//前面 p、q节点换位置了
                    p=q->next;

                }
                //
                q=p;
                p=p->next;
            }
        }
        head =fade_head->next;
        return head;

    }

};

其中的

q->next = p->next; p->next = q;

本想着用swap(p,q)直接偷懒，最后更新下p、q前一个结点的指向关系就ok，结果输出和输入一毛一样，原本还在纠结，p、q 交换后到底交换了什么？到底是p、q节点的内容变了，位置不变【p、q指向发生了变化】，还是内容不变，p、q位置变了【p、q节点位置发生了变化】，自嘲自己一下，交换指针我还是自己手写交换节点位置吧，交换后p、q的指向再换一下，这个思路还是熟悉的。