美文网首页lintcode程序员
451. 两两交换链表中的节点

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

作者: 和蔼的zhxing | 来源:发表于2018-02-01 09:55 被阅读6次

    给一个链表,两两交换其中的节点,然后返回交换后的链表。
    样例
    给出 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;
        }
    

    相关文章

      网友评论

        本文标题:451. 两两交换链表中的节点

        本文链接:https://www.haomeiwen.com/subject/hgnrzxtx.html