链表相干的口试题型总结-

链表相干的口试题型总结

添加时间:2013-6-7 点击量:

链表相干的口试题型总结及其个别实现

对指针的把握程度，是衡量一个法度员的根蒂根基功是否扎实的首要考量标准。而数据布局中的链表、二叉树等根蒂根基数据布局，是查核指针的利器。本文稍微总结了下链表的首要考点，以备将来的求职。

说在前面的重视事项

起首，涉及到指针的编程，对于指针有效性的断定不成忽视，代码中必然要有对NULL指针的断定，如许代码才加倍的鲁棒。

其次，若对链表进行插入，删除操纵，必然要重视更新head指针（和tail指针）的指向。

最后，我们定义结点的数据布局为：

struct Node{
int datum;
Node
next;
};

先总结下我的心得

起首，若是题目对空间错杂度没有什么请求，可以鉴戒hash，额外的数组等，将题目简化

其次，可以应用快慢指针的思惟，设置两个指针，一个指针走得快些或先走几步，就可以或许很好的解决大多半题目。

再者，对于指针的接见操纵，必然要警惕再警惕，必然要确认有效才干持续接见。

最后，涉及到插入，删除操纵，函数中传入的指针参数要设置成 Node，如许才干进行批改操纵。

常考的题型

对于链表，首要查核以下几类项目组：

一、查询断定类

断定两链表是否订交，若订交，返回第一个订交结点

断定链表是否有环

求链表的倒数第 K 个数

二、操纵类

链表排序

链表插入

链表删除结点

若给定欲删除的结点指针，如安在O（1）时候内删除？

有序链表归并

错杂链表复制

题目解析及求解

1.1. 两链表（无环）订交的剖断

思路一：尾地址剖断法。常规的断定办法是断定两链表的最后一个结点地址是否雷同。具体做法是先遍历list1，保存最后一个结点的地址end1；再遍历list2到最后一个结点，断定地址是否便是end1。
时候错杂度为O（len1+len2），空间错杂度为 O（1）。

 1 bool cross_tail_compare（Node h1， Node h2）

 2 {

 3     if（h1 == NULL || h2 == NULL）{

 4         return NULL;

 5     }

 6     Node p = h1;

 7     while（p->next!=NULL）{

 8         p = p->next;

 9     }

10     Node q = h2;

11     while（q->next!=NULL）{

12         q = q->next;

13     }

14     return （p == q）;

15 }

View Code

思路二：hash地址法。凡是若容许应用hash的话，可以或许快速有效的解决。这里，我们遍历list1，将每个结点的地址hash；再遍历list2，断定结点地址是否呈如今hash表中。时候错杂度为O（len1+len2），空间错杂度为O（len1）; 这里，固然时候错杂度未降落，同时增长了空间错杂度，然则却能很好的解决第1个公共结点题目。算是一种抵偿。

思路三：链接成环法。参考下面图3。起首，先将第一个链表的最后一个结点链接到第二个结点的头，然后断定是否有环，如有环，则申明两个链表存在公共结点。

1.2. 链表是否有环的剖断

思路一： 快慢指针法. 我们在用快fast， slow两指针指向链表头，fast指针一次跨两步， slow指针一次跨一步，有环的前提为fast==slow ！= NULL 。

 1 Node fastinCircle（Node head）

 2 {

 3     if（head == NULL）

 4         return NULL;

 5     Node fast = head;

 6     Node slow = head;

 7     while（（fast!=NULL） && （fast->next != NULL） && （slow!=NULL））{

 8         fast = fast->next->next;

 9         slow = slow->next;

10         if（fast == slow）  break;

11     }

12     if（（fast == NULL） || （fast->next == NULL） || （fast != slow）） return NULL;

13     return fast;

14 }

View Code

思路二： hash地址法。遍历链表，将地址hash进来，若NULL了，则申明无环，若存在雷同的地址，则申明有环。且能获得第一个入环的点。时候错杂度为O（len1），空间错杂度为O（len1）。

1.3. 寻找两链表的第一个公共结点

思路一：hash地址法。经由过程1.1的解析，我们可以或许用hash的办法快速获得第一个公共的结点。

思路二：首尾对齐法。若采取尾地址剖断法，我们可以或许获得最后一个公共结点，那么回溯N步同时断定地址是否相等，就能获得第一个公共结点了。可惜是单链表，没有prev指针，然则这个思惟启发了我们，若是两个链表尾对齐了，那么对长链表先next X 步，使头部也对齐，那么，第一个雷同的地址点，就是第一个公共结点了。按照图3，我们可以看出，长链表先走X=（lenMax-lenMin）步后，那么，他们将同时递增到first common 点。时候错杂度为O（len1+len2+x），空间错杂度为O（1）。

Node cross_first（Node h1， Node h2）

{

    if（h1==NULL || h2==NULL）{

        return NULL;

    }

    Node p = h1;

    int s1 = 0;

    while（p->next != NULL）{

        ++s1;

        p = p->next;

    }

    Node q = h2;

    int s2 = 0;

    while（q->next != NULL）{

        ++s2;

        q = q->next;

    }

    if（p != q）

        return NULL;



    p = h1;

    q = h2;

    int prestep = static_cast<int>（abs（s1-s2））;

    if（s1>s2）{

        while（prestep--）{

            p = p->next;

        }

    }else{

        while（prestep--）{

            q = q->next;

        }

    }

    while（p != q）{

        p = p->next;

        q = q->next;

    }

    return p;

}

思路三：链接成环法（也是求环的进口点的解法）。将链表1的尾结点链接到链表2的第一个结点，然后调用快慢指针法断定是否有环。然后保存相遇点，同时slow指针从头开端，步长为1递增；fast指针从相遇点开端，步长为1递增，他们再一次的相遇点，则是第一个公共结点。

数学推导如下：

先假设链表长 L，入环前结点数 b，环内结点 r， slow指针走了 s 步相遇，相遇点为环内 x 步，则 fast 指针走了 2s 步，且相遇点前fast已近走了n（n>=1）圈。则有：

s+nr = 2s
s = nr
s = b + x
r = L - b;
b + x = nr = （n-1）r +r = （n-1）r + L - b
b = （n-1）r + L-b-x

这里，L-b-x 便是相遇点到环结尾的长度，b 为开首到环进口的长度。是以，在链表头和相遇点各设置一个指针，持续走 b 步，就必然能相遇。

Node cross_first_by_circle（Node h1， Node h2）

{

    if（h1 == NULL || h2 == NULL） return NULL;

    Node p = h1;

    while（p->next != NULL）{

        p = p->next;

    }

    Node holdh1 = p;

    p->next = h2;

    Node fast = NULL;

    fast = fastinCircle（h1）;

    if（fast == NULL） return NULL;

    Node slow = h1;

    while（fast != slow）{

        fast = fast->next;

        slow = slow->next;

    }

    p->next = NULL;

    return fast;

}

参考材料：

http://www.cnblogs.com/gw811/archive/2012/10/28/2743182.html

http://wenku.baidu.com/view/299c440cf78a6529647d536b.html

《剑指offer》

1.4 求链表的倒数第K个数

有了前面首尾对齐法和快慢指针的思惟，我们是不是能启发到怎么求倒数第K个数呢？

思路一： 若是双向链表，则很简单，从尾端往回走K步就行。

思路二： 若是单链表，先遍历获得链表的长度，然后逆推出要到倒数k地位，则要走 n-k+1步；

思路三：

很简单，设置两个指针，一个指针从从头先走k-1步，别的个指针再从头开端，那么，当第一个指针达到结尾时，别的个指针正好达到倒数第K个结点。

Node backK（Node head， int k）

{

    if（head == NULL || k <= 0） return NULL;

    Node p = head;

    for（int i=0; i<k-1; ++i）{

        if（p->next == NULL） return NULL;

        p = p->next;

    }

    Node knode = head;

    while（p->next != NULL）{

        p = p->next;

        knode = knode->next;

    }

    return knode;



}

归纳法证实：

若k=1: k-1 = 0，两个指针同步运行，成立。

若k=x; k-1 = x-1; 第一个指针持续走 n-x步达到最后一个结点，第二个指针走（n-x）步后，处于倒数 n-（n-x）=x 的地位，成立。

这里的重视事项是：若链表长度小于k怎么办？输入的是空链表怎么办？若输入k=0，则k-1步导致溢出怎么办？是以，写好一个好的代码是要推敲很多身分的。

2.1 链表排序

对链表排序，想下似乎挺简单的，实际上是很富有挑衅性的。这里我们以单链表为例。

思路一： 若是空间很是充裕的话，我们完全可以鉴戒STL中对deque进行排序时辰的做法，先将元素赋值到vector中，排序后再拷贝回deque。做法也是一样的，遍历链表，把每个元素存入到一个新的数组中，然后对该数组排序（默认应用快排），然后再拷贝回链表（只批改卫星数据）。时候错杂度为O（n+nlgn+n） = O（nlgn），空间错杂度为O（n）；

思路二： 单链表，只能前向移动，我们推敲到简单的排序办法必须是相邻进行斗劲的，合适前提的有插入排序，冒泡排序，甚至，希尔排序也是可以的。同时，排序算法内部的轮回也必须是前向移动才行。

2.2 链表插入

对于链表插入操纵，分为头插法和尾插法。若是排序好的链表插入，还要定位到响应的地位。

 1 Node _front（Node head， int value）

 2 {

 3     if（head == NULL）

 4         return NULL;

 5     if（head == NULL）{

 6         head = new Node（value）;

 7     }else{

 8         Node p = new Node（value）;

 9         p->next = head;

10         head = p;

11     }

12     return head;

13 }

14 Node _comp（Node head， int value）

15 {

16     if （head == NULL）

17         return NULL;

18     Node in;

19     if （head == NULL） {

20         in = new Node（value）;

21         head = in;

22     }else{

23         in = new Node（value）;

24         if（（head）->datum > value）{

25             _front （head， value）;

26         }else{

27             Node p = head;

28             Node n = （head）->next;

29             while（ n != NULL && n->datum < value）{

30                 p = n;

31                 n = n->next;

32             }

33             p->next = in;

34             in->next = n;

35         }

36     }

37     return in;

38 }

2.3 链表删除某一节点

对于删除操纵，简单的来说，就是两个指针，一前一后，后的一个达到删除点后，操纵就很简单了。还有个办法，见2.4.

2.4 单位时候内删除节点（节点指针给定）

对于这个，一般凡是的做法是采取2.3的做法，然则这个时候错杂度为O（n）。可以参考下<剑指offer>中介绍的办法，我们先画图来说下：

图4的上半项目组是我们凡是（2.3）的做法，须要前一个指针帮助删除；

图4下半项目组的删除，就不须要了。做法如下：

起首来个帮助指针q指向下一个结点。将q的数据域赋给cur，然后更新cur.next，最后删除q。如许，就能在O（1）的时候内删除结点了。

 1 void delNode（Node head， Node n）

 2 {

 3     if（head == NULL || head == NULL || n == NULL）

 4         return;

 5     if（n->next != NULL）{ // 删除的不是尾结点;

 6         Node tmp = n->next;

 7         n->datum = tmp->datum;

 8         n->next = tmp->next;

 9          tmp;

10         tmp = NULL;

11     }else if（head == n）{   // 仅有一个结点

12          n;

13         head = NULL;

14     }else{                    // 删除尾结点

15         Node p = head;    

16         while（p->next != n）{

17             p = p->next;

18         }

19         p->next = NULL;

20          n;

21         n = NULL;

22     }

23 }

2.5 有序链表归并

这个可以参考下STL中的接合函数的写法。

2.6 错杂链表复制

参考下<剑指offer>

测试函数：

 1 void show（const Node head， const Node end = NULL）

 2 {

 3     if（head == end） return;

 4     const Node p = head;

 5     while（p != end）{

 6         cout << p->datum << --> ;

 7         p = p->next;

 8     }

 9     if（end == NULL）

10         cout << NULL << endl;

11     else{

12         cout << end->datum << endl;

13     }

14 }

打印函数

 1 ＃include myslist.h

 2 ＃include <iostream>

 3 using namespace std;

 4 int main（）

 5 {

 6     Node head1 = NULL;

 7     _comp （&head1， 1）;

 8     _comp （&head1， 2）;

 9     _comp （&head1， 3）;

10     _comp （&head1， 7）;

11     _comp （&head1， 15）;

12     Node head2 = _comp （&head1，6）;

13     _front（&head2，5）;

14     _front（&head2，4）;

15     show（head1）;

16     show（head2）;

17     cout << Is cross？  << cross_tail_compare （head1，head2） << endl;

18     cout << The first cross point by cross_first:  << cross_first （head1，head2）->datum << endl;

19     cout << The first cross point by cross_first_circle:  << cross_first_by_circle （head1，head2）->datum << endl;

20     cout << back 5s node of head1 is:  << backK （head1，5）->datum << endl;

21     Node pp = fastinCircle （head2）;

22     if（pp == NULL）{

23         cout << No circle << endl;

24     }else{

25         cout << circle << endl;

26     }

27     cout << -----------Test Circle--------------- << endl;

28     Node head3 = NULL;

29     _comp （&head3， 1）;

30     _comp （&head3， 2）;

31     Node circin = _comp （&head3， 3）;

32     _comp （&head3， 7）;

33     Node tail = _comp （&head3， 15）;

34     tail->next = circin;

35     show（head3，tail）;

36     show（tail，tail->next）;

37     pp = fastinCircle（head3）;

38     if（pp == NULL）{

39         cout << No circle << endl;

40     }else{

41         cout << circle << endl;

42     }

43     return 0;

44 }

读书，不要想着实用，更不要有功利心。读书只为了自身的修养。邂逅一本好书如同邂逅一位知己，邂逅一个完美之人。有时心生敬意，有时怦然心动。仿佛你心底埋藏多年的话，作者替你说了出来，你们在时光深处倾心相遇的一瞬间，情投意合，心旷神怡。

分享到：

相关文章

按版本划分

按功能划分

企业管理软件