Linked Lists

花2天把Leetcode上Linked lists的题目刷完了,下面是一些我觉得比较有倾诉欲望的题。

237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

这道题我的第一反应是,it's impossible!只给了这个node,鬼知道它前面那个node是啥呀,这不是怎么都找不到的么。后来看了答案觉得真是骨骼清奇,它采取的并不是寻常的找到前一个node,改变pointer这样的方式,而是很tricky地,先将这个node的值改成下一个node的值,然后删掉下一个node。不过话说回来,这道题我觉得并不是很合理,严格来说这不算删掉了这个node,它删掉的是下一个node,不太严谨。不过当做一种思路的扩充吧。

class Solution {
public:
    void deleteNode(ListNode* node) 
    {
        node->val = node->next->val;
        ListNode* next = node->next->next;
        delete node->next;
        node->next = next;
    }
};

206. Reverse Linked List

Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

这题我觉得很好,用两种方式来翻转链表,越基础越是需要掌握。

Iteratively的做法,如果不借助其他pointer的帮助,我们只能每次都从头找到尾,太笨了。如果设置一个prev pointer,那么对cur node来说,前后关节打通了,实际上成为了一个双向链表,操纵一下pointer就可以实现翻转了,不是什么难事。这里的思想方法其实就是把单向链表转化为双向链表来做。

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* prev = nullptr;
        ListNode* next;
        while (head)
        {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

Recursively的做法,比前者稍微难一点。这个方法我并没有自己想出来,我的思路是:要翻转这个链表,肯定要先翻转cur->next这个链表……这么下去到最后一个链表返回的就是最后一个node。我们需要实现:return node->next = head,但是最后我们需要返回的结果却是最后一个node,这就要求我们能return两个值,无法实现。所以我就卡住了。

这种思路其实也挺正常的,但是当思路不对的时候,应该再想想有没有其它思路——这点也许是我欠缺的。答案中,我们return node就是最后一个node,那么难点就在于如何将head和后面一个已经反转的链表联系起来。其实稍微想一想就得出,head->next->next = head就可以实现目标了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (!head || !head->next) return head;
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

其实再仔细一想,作为一个recursion,写的时候其实可以把结构都先描画出来,像列提纲一样,就是把recurse()和return x;写好在那边,那目标就很明确,我们在利用recursion解决什么subproblem,我们最后要返回的是什么。我们最后要返回的是什么,这点在recursion中至关重要,却也最容易迷失。recursion的问题其实就是假设这个recursion works,subproblem已经解决了,对于解决这个整个问题有什么用处,recursion就像一个api一样,是让我们去调用的,最终在于返回一个结果。当我们将最后我们要返回什么搞清楚,很多时候问题就清楚了。

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

这道题利用了Floyd's hare and tortoise algorithm来找到cycle。以下的证明供我自己容易理解、记住而得:

  • 算法:已知一个链表存在循环,用两个指针,一快一慢,快的速度是慢的两倍,从头开始iterate这个链表,那么它们一定会在某一个node相遇。

  • 证明:最intuitive的思想:当慢指针刚刚进入循环,快指针已经进入循环中的某一个节点了,因为快慢指针相对速度差一个节点,慢指针进步一格,快指针进步两格,这相当于说慢指针不动,快指针进步一格,这样快指针肯定能追上慢指针,它们一定会相遇。

  • 算法:将快指针放到链表开头,慢指针依旧在两者相遇处,每次两格指针同时前进一格,第二次它们相遇的节点,就是循环的开始。

  • 证明:令循环长度为n,进入循环前的长度为x,循环开始到相遇地距离为y,相遇地到循环开始距离为z。到相遇时,慢指针走过的距离是d=x+y,快指针走过的距离是D=x+y+kn。假如k>1,那么说明快指针

与#142题相结合,以下是检测有无cycle以及返回cycle开始的节点的代码:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* copy = head, *slow = head, *fast = head;
        while (fast && fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next || !fast->next->next) return nullptr;
        slow = head;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

时间复杂度为O(N+K),其中N是循环起点之前的node数,K是循环node数。因为在循环中转了一圈之后,快指针肯定能追上慢指针了。空间复杂度为O(1)。

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

这道题我有几种思路:
1、延续前面讨论过的龟兔赛跑算法,完全可以找出这个node,也就是循环开始的这个node。当然,用这种方法要先构造出一个环路,最后把结构还原就行了。
2、可以通过判断最后一个节点是否一样来判断两个链表有无交集。如果有交集,可以通过计算长度来判断交集点。因为从交集开始到结尾,两个链表的长度一样,那么两个链表长度之差,也就是两个链表从开头到交集长度的差。所以我采取的方法是,将长度都算出来,将较长的那个链表的指针往前移difference位,然后两个指针一起出发,相交点即为所求节点:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        if (!headA || !headB) return nullptr;
        ListNode *copy_A = headA, *copy_B = headB;
        int len_A = 0, len_B = 0;
        while (headA->next) { headA = headA->next; ++len_A; }
        while (headB->next) { headB = headB->next; ++len_B; }
        if (headA != headB) return nullptr;
        int dif = abs(len_A - len_B);
        if (len_A > len_B) 
        {
            while (dif--) copy_A = copy_A->next;
        }
        else 
        {
            while (dif--) copy_B = copy_B->next;
        }
        while (copy_A->next)
        {
            if (copy_A == copy_B) return copy_A;
            copy_A = copy_A->next;
            copy_B = copy_B->next;
        }
        return copy_A;
    }
};

这个代码很长很难看,后来去discussion区看了一下,有更精简的表述方法:原解答网址。Code摘抄如下:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
    ListNode *p1 = headA;
    ListNode *p2 = headB;
        
    if (p1 == NULL || p2 == NULL) return NULL;

    while (p1 != NULL && p2 != NULL && p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;

        // 如果从链表开头到交集的长度一致,那么这一行就返回所找到交集节点
        // 当两者没有交集,也用了这一行
        if (p1 == p2) return p1; 
    
        // 如果短链表提前走完了,将指针置于长链表开端
        // 等到长链表的指针也走完了,将指针置于短链表开端
        // 而这时候,之前放置的长链表指针已经多走了difference步了
        if (p1 == NULL) p1 = headB; 
        if (p2 == NULL) p2 = headA;
    }
        
    return p1;
}

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

这道题的code很简单不贴了,思维过程值得回顾一下。

分析题意:

  • deep copy:
    • 说明需要新建node,而不只是对pointer的操纵
    • 说明原来的node不能变动
  • next pointer没什么花头,关键点在于怎么去对应这个random pointer。由于原来的random pointer指的是原来的node list中的node,现在的random pointer指的是新node list中的node,需要一种方法将原来的node和新的node一一对应

我一开始做的时候,想的是,将原来node的next pointer指到对应的现在node,现在node的random pointer指到原来node。这样一来,上下互通。但是这个问题是,一旦现在node的random pointer被修改了以后,就无法复原原来的pointer。所以这种方法不对。

看了答案,是将新node插入进两个老node里。另外值得注意的是,写code的时候对于nullptr这种情况要分外注意,有两次提交失误都是因为没有注意nullptr。

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

这道题是检验前面几题有没有白做了的范例。前面几题用到的知识中最重要的亮点——fast/slow pointer; use a prev pointer in singly linked list。将这两点与这题相结合,得出方法:用slow/fast pointer法+reverse list法将前半个list翻转,然后从中间向两边对照数字。其中注意奇偶不同和nullptr的检验。

19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

巨喜欢这道题,因为它很灵活地考察了fast slow pointer。看到这道题的时候,我知道找到这个node之后,操纵pointer是很轻松的事情。主要是怎么来找到这个node。如果N是开头到这个node的距离,那么一遍就能找到并且删掉。现在N是node到结尾的距离,我第一反应肯定要用到fast slow pointer,但是两倍的fast slow pointer很难应用啊。然后想了几种很复杂的方法,觉得不太符合题目“in one pass”的要求。然后也有点赶时间,就看答案了。

我来试图模拟得到这个答案的思维过程:如果node到结尾的距离是N,整个list长L,那么从开头到这个node的距离是L-N。也就是让pointer走L-N距离就可以找到这个node了。让pointer走L-N距离有两种方法,一种是从开头走到这个node,一种是从开头+N走到最后。所以我们只要先将fast pointer往前挪N,然后跟slow pointer一起每次一格走到最后,slow pointer所得到的就是要被删的node。

这道题属于灵活应用的“微创新”题,真的很喜欢,希望下次自己能想出来。砰砰砰。

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这道题其实挺有意思的。从merge two lists到merge k lists,第一个想到的是divide and conquer,把问题分解成merge two lists就好了。这样的解法空间复杂度是O(logk),k是lists中list的数量,时间复杂度是O(nlogk),n是总共的node数,因为每一层merge的时候复杂度都是O(n),一共有logk层。另外还有一种解法是用priority queue,这个利用了priority queue的自带sorting性质,每次我们将list的开头push到这个queue里,queue里最多有k个node。code挺简单的就不贴了。关于priority queue的底层implementation抽空再复习一下。

<Reorder list>

有不少题是关于调换linked list中元素的位置的,甚至是将list转换为tree。这种题啊换汤不换药。快慢指针、设置prev pointer,可以说是套路至极了。

总结:
1、多想想fast/slow pointer,其中包括fast pointer比slow pointer跑的快一倍的(用于找中间数,找到cycle等),也包括fast比slow跑的不是两倍的。这两个指针可以用来解决很多在单向链表中关于距离的问题。
2、对于singly linked lists, 多想想设置一个prev pointer使之成为本质上的doubly linked lists
3、小心犯错误的code detail:
1)在操纵pointer的时候,小心前面的pointer变化影响到后面
2)考虑nullptr的情况
3)对一个node的前后node要多检查

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,179评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,229评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,032评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,533评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,531评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,539评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,916评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,813评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,568评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,654评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,354评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,937评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,918评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,152评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,852评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,378评论 2 342

推荐阅读更多精彩内容