lintcode程序员

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

2018-02-01  本文已影响6人  和蔼的zhxing

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

猜你喜欢

热点阅读