美文网首页
链表问题

链表问题

作者: _假行僧_ | 来源:发表于2020-09-24 14:31 被阅读0次

    前言

    如果说数据结构是算法的基础,那么数组和链表就是数据结构的基础。 因为像堆,栈,对,图等比较复杂的数组结基本上都可以由数组和链表来表示,所以掌握数组和链表的基本操作十分重要。

    概述

    与数组相似,链表也是一种线性数据结构。这里有一个例子:


    单链表.png

    正如你所看到的,链表中的每个元素实际上是一个单独的对象,而所有对象都通过每个元素中的引用字段链接在一起。
    链表有两种类型:单链表和双链表。上面给出的例子是一个单链表,这里有一个双链表的例子:


    双链表.png
    本文主讲单连表的操作,以及一些题目。

    节点结构

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

    在大多数情况下,我们将使用头结点(第一个结点)来表示整个列表。

    操作

        与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。
    

    主要连个操作:添加和删除。

    添加操作-单链表

    如果我们想在给定的结点 prev 之后添加新值,我们应该:
    使用给定值初始化新结点 cur;


    添加1.png

    将 cur 的 next 字段链接到 prev 的下一个结点 next ;


    添加2.png
    将 prev 中的 next 字段链接到 cur 。
    添加3.png
    与数组不同,我们不需要将所有元素移动到插入元素之后。因此,您可以在 O(1) 时间复杂度中将新结点插入到链表中,这非常高效。
    删除操作 - 单链表

    如果我们想从单链表中删除现有结点 cur,可以分两步完成:
    找到 cur 的上一个结点 prev 及其下一个结点 next

    删除1.png
    接下来链接 prev 到 cur 的下一个节点 next
    删除2.png
    在我们的第一步中,我们需要找出 prevnext。使用 cur 的参考字段很容易找出 next,但是,我们必须从头结点遍历链表,以找出 prev,它的平均时间是 O(N),其中 N 是链表的长度。因此,删除结点的时间复杂度将是 O(N)
    空间复杂度为 O(1),因为我们只需要常量空间来存储指针。
    常见题目(leetcode)

    1.链表翻转
    反转一个单链表。
    示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
    思路:
    1->2->3->4->5->.....
    1<-2<-3 4->5->....
    逐个断开链表节点,使其next指针指向前一个节点,其中head节点的next指向NULL.
    从上述不难注意到,我们在调整一个节点的next指针时,除了要知道节点本身,还需要知道当前节点的前一个节点,因为我们需要把next指针指向前一个节点,以完成反转,同时,还需要保存当前节点的下一个节点以防止链表断开。
    代码如下:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if(head==nullptr) return head;
            ListNode* pre=head;
            ListNode* cur=pre->next;
            pre->next=nullptr;
            while(cur!=nullptr)
            {
                ListNode* curNext=cur->next;
                cur->next=pre;
                pre=cur;
                cur=curNext;
            }
            head=pre;
            return head;
        }
    };
    
    链表双指针

    让我们简单看一下一下这种技巧。 我们提到了两种使用双指针技巧的情景:
    1.两个指针从不同位置出发:一个从始端开始,另一个从末端开始;
    2.两个指针以不同速度移动:一个指针快一些,另一个指针慢一些。
    对于单链表,因为我们只能在一个方向上遍历链表,所以第一种情景可能无法工作。然而,第二种情景,也被称为慢指针和快指针技巧,是非常有用的。

    相交链表和环形链表

    2.相交链表
    编写一个程序,找到两个单链表相交的起始节点。


    相交链表.png

    -如果两个链表没有交点,返回 null.
    -在返回结果后,两个链表仍须保持原有的结构。
    -可假定整个链表结构中没有循环。
    -程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
    方法1:
    定义连个指针分别指向a和b两个链表的头结点pa,pb,分别遍历链表到尾端计算长度lengthA和lengthB,链表长的先走|lengthA-lengthB|步,让后同时走,若存在pa==pb怎有交点,否则两链表不想交。代码:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA==nullptr || headB==nullptr) return nullptr;
            int lenA=0,lenB=0;
            ListNode* pA=headA;
            ListNode* pB=headB;
            while(pA!=nullptr)
            {
                lenA++;
                pA=pA->next;
            }
            while(pB!=nullptr)
            {
                lenB++;
                pB=pB->next;
            }
            pA=headA;
            pB=headB;
            if(lenA>lenB)
            {
                int diff=lenA-lenB;
                while(diff>0)
                {
                    pA=pA->next;
                    diff--;
                }
            }
            else
            {
                int diff=lenB-lenA;
                while(diff>0)
                {
                    pB=pB->next;
                    diff--;
                }
            }
            while(pA!=nullptr && pB!=nullptr)
            {
                if(pA==pB) return pA;
                pA=pA->next;
                pB=pB->next;
            }
            return nullptr;
        }
    };
    

    方法2:
    一种比较巧妙的方式是,分别为链表A和链表B设置指针A和指针B,然后开始遍历链表,如果遍历完当前链表,则将指针指向另外一个链表的头部继续遍历,直至两个指针相遇。
    最终两个指针分别走过的路径为:
    指针A :a+c+b
    指针B :b+c+a
    明显 a+c+b = b+c+a,因而如果两个链表相交,则指针A和指针B必定在相交结点相遇。
    代码:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
           if(headA==nullptr || headB==nullptr) return nullptr;
            int lenA=0,lenB=0;
            ListNode* pA=headA;
            ListNode* pB=headB;
            while(pA!=nullptr || pB!=nullptr)
            {
                if(pA==pB) return pA;
                pA=pA->next;
                pB=pB->next;
                if(pB==nullptr && pA==nullptr) break;
                if(pA==nullptr) pA=headB;
                if(pB==nullptr) pB=headA;
            }
            return nullptr;
        }
    };
    

    3.环形链表
    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。


    环形链表.png

    如果有环,此时快慢指针都在环上,假如快指针离慢指针相差 N 个结点(N大于2),则下一次遍历由于慢指针走一步,快指针走两步,所以相差 N+1-2 = N-1 个结点,发现了吗,相差的结点从 N 变成了 N-1,缩小了!不断地遍历,相差的结点会不断地缩小,当 N 缩小为 1 时,慢指针走一步,快指针走两步,则快指针追上慢指针此时相遇,由此得证,如果有环,快慢指针一定会相遇 。
    要找到入口结点,只需定义两个指针,一个指针指向head, 一个指针指向快慢指向的相遇点,然后这两个指针不断遍历(同时走一步),当它们指向同一个结点时即是环的入口结点。

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(head==nullptr) return nullptr;
            ListNode* slow=head;
            ListNode* fast=head;
            ListNode* meetNode=nullptr;
            while(fast!=nullptr && fast->next!=nullptr)
            {
                fast=fast->next->next;
                slow=slow->next;
                if(fast==slow) break;
            }
            if(fast==nullptr || fast->next==nullptr)
            {
                return nullptr;
            }
            slow=head;
            while(slow!=fast)
            {
                slow=slow->next;
                fast=fast->next;
            }
            return slow;
        }
    };
    

    相关文章

      网友评论

          本文标题:链表问题

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