您好,登录后才能下订单哦!
本篇内容主要讲解“分析链表和递归问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“分析链表和递归问题”吧!
链表具有天然的递归性,一个链表可以看出头节点后面挂接一个更短的链表,这个更短的链表是以原链表的头节点的下一节点为头节点,依次内推,直到最后的更短的链表为空,空本身也是一个链表(最基础的)。
以单链表 1->2->3->null 为例子,如下图示:
原链表
将原链表看出头节点 1 后挂接一个更短的链表
头节点+更短链表
继续拆解,直到无法拆解
更更短链表
更更更短链表
有了这样的思考,很多「链表」相关问题,都可以采用「递归」的思路来解答。
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制: 0 <= 节点个数 <= 5000
要反转链表,即将原链表的头节点变为新链表的尾节点,原链表的尾节点变为新链表的头节点。如下图示:
反转之前:
原链表
反转之后:
新链表
主要策略主要有:1、直接修改链表的值,如上图中的原链表图所示,将原链表值 1 的头节点改为原链表尾节点的值,依次类推;2、让遍历整个链表,让链表的尾节点指向其前一个节点,依次类推。
虽然这两个策略都可行,不过在面试中通常要求采用「策略2」。
由上面的「递归与链表」可知,本题也可以采用「递归法」去求解。
具体如何通过「递归」去解答呢?见下面例子。
「举例」
链表 1->2->3->null 为例子,如下图示。
示例
不断遍历找到原链表为尾节点,即新链表的头节点。
原链表尾节点
然后让尾节点指向其前驱节点,依次类推。
递归反转
详细步骤,如下动图示:
递归反转单链表
「C」
struct ListNode* reverseList(struct ListNode* head){ /* 递归终止条件 */ if (head == NULL || head->next == NULL) { return head; } /* 反转当前所在的链表节点 */ struct ListNode* newHead = reverseList(head->next); /* 由原链表的尾节点挨个指向其前驱节点 */ head->next->next = head; /* 防止成环 */ head->next = NULL; /* 返回新的链表头节点 */ return newHead; }
「java」
ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; }
当然本题也可以采用「迭代」的方法去做,其代码(python 版)也很优雅,具体如下:
「python」
def reverseList(self, head: ListNode) -> ListNode: cur, pre = head, None while cur: cur.next, pre, cur = pre, cur, cur.next return pre
「复杂度分析」
时间复杂度:「O(n)」,n 是链表的长度。对链表的每个节点都进行了反转操作。
空间复杂度:「O(n)」,n 是链表的长度。递归调用的栈空间,最多为 n 层。
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]
要移除链表中给定值的节点,一般策略是「找到给点值的节点的前驱节点,然后让其指向给定值的节点的后继节点」。
例如要删除链表 1->2->3->null 中,节点值为 3 的节点,就得先找到其前驱节点(值为 2 的节点),如下图示:
删除给定值的节点
由上面的「递归与链表」可知,本题同样也可以采用「递归法」去求解,不断删除更短链表中给定值的节点,然后再将处理后的更短的链表,挂接在其前驱节点后。
「注意」最后要判断原链表的头节点是否是待移除的节点。
「举例」
以链表 1->2->3->null 为例子,移除链表中给定值的节点的过程,如下动图示。
示例动图
「C++」
ListNode* removeElements(ListNode* head, int val) { /* 递归终止条件 */ if(head == NULL) { return NULL; } /* 删除链表中头节点后值为 val 的元素的节点 */ head->next=removeElements(head->next,val); /* 判断头节点是否为值为 val 的节点,再返回*/ return head->val==val ? head->next : head; }
「Golang」
func removeElements(head *ListNode, val int) *ListNode { if head == nil { return head } head.Next = removeElements(head.Next, val) if head.Val == val { return head.Next } return head }
「复杂度分析」
时间复杂度:「O(n)」,n 是链表的长度。递归需要遍历链表一次。
空间复杂度:「O(n)」,n 是链表的长度。递归调用栈,最多不会超过 n 层。
到此,相信大家对“分析链表和递归问题”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。