526互联

leetcode day4 24 19 面试题02.07 142

发布时间 2023-07-15 23:46:08作者: LiviaYu

目录

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


if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        //ans指针，永远指向head，返回值
        ListNode * ans=new ListNode(-1,head);
        //指向前一个
        ListNode * pre=ans;
        //指向中间一个
        ListNode * cur=head;
        ListNode * next=head->next;
        while(1)
        {
            //前一个结点指向next
            pre->next=next;
            //中间节点指向next的下一个节点
            cur->next=next->next;
            //next节点指向中间节点
            next->next=cur;
            //pre节点后移到中间节点
            pre=cur;
            //如果不为空就继续循环
            if(cur->next!=nullptr)
            {
              cur=cur->next;  
            }
            else
            {
                break;
            }
            if(cur->next!=nullptr)
            {
                next=cur->next;
            }
            else
            {
                break;
            }
        }
        return ans->next;

19.删除链表的倒数第N个节点

比较简单，主要思路就是先计算整个链表的长度，用长度减去n，得到要移除节点的位置，再移除节点

ListNode * ans=new ListNode(-1,head);
        ListNode * temp=new ListNode(-1,head);
        if(head->next==nullptr)
        {
            return nullptr;
        }
        //计算移动的距离
        int size=0;
        while(temp->next!=nullptr)
        {
            size++;
            temp=temp->next;
        }
        ListNode * temp1=ans;
        int max=size-n;
        //定位要移除节点的位置
        for(int i=0;i<max;i++)
        {
            temp1=temp1->next;
        }
        //移除节点
        temp1->next=temp1->next->next;
        return ans->next;

面试题 02.07. 链表相交

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，
如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

ListNode * A=headA;
        ListNode * B=headB;
        int lenA=0;
        int lenB=0;
        while(A!=nullptr)
        {
            A=A->next;
            lenA++;
        }
        while(B!=nullptr)
        {
            B=B->next;
            lenB++;
        }
        int gap=abs(lenA-lenB);
        A=headA;
        B=headB;
        if(lenA>lenB)
        {
            while(gap--)
            {
                A=A->next;
            }
            while(lenB--)
            {
                if(A==B)
                {
                    return A;
                }
                A=A->next;
                B=B->next;
            }
        }
        else{
            while(gap--)
            {
                B=B->next;
            }
            while(lenA--)
            {
                if(A==B)
                {
                    return A;
                }
                A=A->next;
                B=B->next;
            }

        }
        return nullptr;

142

通过unordered_set来确定是否被访问过

unordered_set<ListNode *> visited;
        while(head!=nullptr)
        {
            if(visited.count(head))
            {
                return head;
            }
            visited.insert(head);
            head=head->next;

        }
        return nullptr;