451. 两两交换链表中的节点

给一个链表,两两交换其中的节点,然后返回交换后的链表。
样例
给出 1->2->3->4, 你应该返回的链表是 2->1->4->3
你的算法只能使用常数的额外空间,并且不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

链表处理

链表的插入要正确处理,还要处理奇数个节点和偶数个节点的不同,细节都在注释里了,自己挑个小的链表画一下,主要是一些边界条件弄对就行了。
另外,我自己写链表的时候喜欢用假节点,不爱动链表本身,假节点初始化的时候一定要给一个值。c++不允许使用未初始化的对象。

ListNode * swapPairs(ListNode * head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *first=new ListNode(0);     //假表头,记得初始化
        first->next=head;
        ListNode *last=new ListNode(0);        //最指向后一个元素,记得初始化
        last->next=first;
        ListNode *tmp;
    
        while(head!=NULL)
        {
            tmp=head;
            if(tmp->next==NULL)      
            //处理只剩一个的情况,要不下面取head=head->next->next的时候就会有野指针
            {
                Insert(last,tmp);
                break;
            }
            head=head->next->next;
            if(tmp->next!=NULL)
            Insert(last,tmp->next);
            Insert(last,tmp);
        }
        
        return first->next;
         
         // write your code here
    }
    void Insert(ListNode *last,ListNode *l)    //插入,last来记录最后一个节点的位置
    {
        ListNode *tmp1=last->next;
        tmp1->next=l;
        l->next=NULL;
        last->next=l;
    }
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容