免费拍卖网站模板,招投标中网站建设评分标准,公众号 微网站建设方案,中国正规现货交易平台准备重启尘封一年的博客作为学习笔记#xff0c;看看自己能坚持多久。 最近会记录做过的算法题#xff0c;语言描述只用于会意#xff0c;仅供参考。 文章目录0.从尾到头获取链表的值#xff08;不是反转链表#xff09;1.寻找/删除单链表倒数第k个节点3.寻找单链表的中点…准备重启尘封一年的博客作为学习笔记看看自己能坚持多久。 最近会记录做过的算法题语言描述只用于会意仅供参考。 文章目录0.从尾到头获取链表的值不是反转链表1.寻找/删除单链表倒数第k个节点3.寻找单链表的中点4.判断链表是否成环 / 求成环链表的起点5.判断两个链表是否相交6.反转整个链表迭代法递归法**7.反转链表的从第left到第right个节点迭代法递归法8.K个一组反转列表9.判断回文链表10.复制复杂的链表11 链表加法0.从尾到头获取链表的值不是反转链表
解答思路
最直观的想法是遍历链表求出长度创建空数组再遍历链表将每个节点的值反向填进数组递归解法很简洁思路类似于树的后根遍历先根-递归过程自顶向下后根-递归过程自底向上从想象一棵单叉的树其实就是链表叶节点向根节点前进就能得到反向的顺序
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:# 返回从尾部到头部的列表值序列例如[1,2,3]def printListFromTailToHead(self, listNode):if listNode is None:return []return self.printListFromTailToHead(listNode.next) [listNode.val]1.寻找/删除单链表倒数第k个节点
使用两个指针forward backward起始时都指向头节点首先让forward指针向前k步到达第k1个节点然后让两指针以相同速度前进直到forward为None此时的backward指向的就是倒数第k个节点。对于删除问题需要额外引入一个指针指向backward之前的节点。此时会出现特殊情况如果倒数第k个节点是链表的头节点则需要特殊处理。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 特判if (head.next null n 1) {return null;}ListNode a head;ListNode b head;ListNode pre_b null;// 先走afor (int i0; in; i) {a a.next;}// ab同时走直到a到达末尾while (a ! null) {pre_b b;a a.next;b b.next;}// 得到b是待删除结点// 如果b是首个元素返回b.nextif (pre_b null) {return b.next;}// b非首个元素pre_b.next b.next;return head;}
}3.寻找单链表的中点
使用快慢指针法。每次步进fast走两步slow走一步当fast或fast.next指向None时slow即为中点。如果链表长度为偶数则slow指向中间并靠后的节点注意循环判断条件 fast ! null fast.next ! null
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) { // 注意判断条件slow slow.next;fast fast.next.next;}return slow;}
}4.判断链表是否成环 / 求成环链表的起点
快慢指针。如果fast最终能遇见None则不成环。如果slow最终能遇见fast则成环。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (fast slow) {return true;}}return false;}
}要求成环链表的起点需要在fast和slow相遇时将一个指针指向链表头再让两指针以1步长前进直到相遇相遇点即为环起点。 假设首次相遇时fast比slow多走了k步则这k步一定是在环内绕圈即k是环长度的整数倍。此时让一个指针回到头节点共同前进k-m步后一定会在环起点相遇。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next;if (fast ! null) {fast fast.next;}// 有环if (fast slow) {fast head;} else {continue;}while (fast ! slow) {fast fast.next;slow slow.next;}return fast;}// 无环return null;}
}5.判断两个链表是否相交
关键在于解决两个链表的对齐问题。解决办法是将链表A的末尾指向链表B的头节点同理B的末尾指向A的头节点。使用两个指针a、b分别从A和B的头节点开始步进直到遇见相同节点。直观思路 对于a走过A的独有部分-相交部分-B的独有部分-相交部分 对于b走过B的独有部分-相交部分-A的独有部分-相交部分如果两个链表不相交则 pa 和 pb 在对方末尾的 None 相等返回 None
class Solution(object):def getIntersectionNode(self, headA, headB)::type head1, head1: ListNode:rtype: ListNodepa headApb headBwhile (pa ! pb):pa pa.next if pa is not None else headBpb pb.next if pb is not None else headAreturn pa6.反转整个链表
迭代法
对于每个节点分为三个步骤
temp node.next // 记录当前节点的下个节点防止修改后找不到
node.next pre // 反转
pre node // 步进
node temp // 步进/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 迭代ListNode temp head; // 从head开始处理head.next最后指向nullListNode pre_temp null;while (temp ! null) {ListNode next_node temp.next; // 保存temp.next pre_temp; // 更改指针pre_temp temp; // 步进temp next_node;}return pre_temp;}
}递归法**
来自拉不拉东的算法小抄写递归算法的关键是明确函数的定义是什么“相信定义”用其推导出最终结果而不陷入递归的细节。搞清楚根节点该做什么剩下的交给前中后序遍历写递归时要有遍历树的思想。下面的代码即为树的后根遍历反转等操作类似题1都能用后根的思想解决
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def reverseList(self, head)::type head: ListNode:rtype: ListNode# 递归出口if head is None or head.next is None:return headreversed self.reverseList(head.next)head.next.next headhead.next Nonereturn reversed7.反转链表的从第left到第right个节点
迭代法
首先定位到第left个节点记录边界并执行right-left次反转
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def reverseBetween(self, head, left, right)::type head: ListNode:type left: int:type right: int:rtype: ListNodedummy ListNode(val-1, nexthead)pre_node dummytemp_node head# 移动到第left个节点for i in range(left-1):pre_node temp_nodetemp_node temp_node.next# 记录左侧未被反转的最后一个节点和被反转的第一个节点forward_last_node pre_nodereverse_first_node temp_node# 从开始反转的第二个节点开始改变连接关系pre_node pre_node.nexttemp_node temp_node.next# 执行反转for i in range(right-left):temp temp_node.nexttemp_node.next pre_nodepre_node temp_nodetemp_node temp# 连接reverse_first_node.next temp_nodeforward_last_node.next pre_nodereturn dummy.next递归法
首先写一个反转头部前N个节点的函数reverseN
ListNode reverseBetween(ListNode head, int m, int n) {// 递归出口if (m 1) {return reverseN(head, n);}head.next reverseBetween(head.next, m - 1, n - 1);return head;
}8.K个一组反转列表
class Solution:def reverseKGroup(self , head , k ):# write code hereif not head or k 1:return headdummy ListNode(-1)node head last_left None while (self.enough(node, k)): # 每次反转k个pre node cur node.next# 执行反转for _ in range(k - 1):temp cur.nextcur.next pre pre cur cur temp if node head: # 记录返回结果dummy.next pre # 处理边界if last_left:last_left.next pre last_left node node cur if last_left: # 连接最后不到k个不反转的last_left.next node return dummy.next if last_left else head # 判断从当前节点开始是否够k个def enough(self, node, k):cnt 0while node:node node.nextcnt 1if cnt k:return True return False 就这么做
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode prevLeftNode null; // 记录上一组反转后的最后节点ListNode res null; // 记录结果ListNode prev head;ListNode curr head.next;while (this.hasKNodesLeft(prev, k)) {ListNode groupHead prev; // 记录当前组反转前的首个节点// 组内反转k-1次for (int i 0; i k - 1; i) {ListNode temp curr.next;curr.next prev;prev curr;curr temp;}// 更改和前一组的指针if (prevLeftNode ! null) {prevLeftNode.next prev; // 非第一组改变指向} else {res prev; // 第一组记录结果}// 更改循环条件prevLeftNode groupHead;prevLeftNode.next curr; // 先把上一组的最后值指向下一组可能不够k个的首个位置如果够k个再修改prev curr;curr curr null ? null : curr.next; // 避免下一组无元素}return res;}/* 判断是否足够k个节点 */public boolean hasKNodesLeft(ListNode node, int k) {int count 0;while (node ! null count k) {count 1;node node.next;}return count k ? true : false;}
}9.判断回文链表
方法一使用递归使用树的后根遍历思想实现栈“后进先出”的功能。
// 左侧指针
ListNode left;boolean isPalindrome(ListNode head) {left head;return traverse(head);
}boolean traverse(ListNode right) {if (right null) return true;boolean res traverse(right.next);// 后序遍历res res (right.val left.val);left left.next;return res;
}方法二利用快慢指针寻找中点反转中点以后的链表并进行比较推荐
class Solution(object):def isPalindrome(self , head ):if not head:return True slow, fast head, head while (fast):slow slow.next fast fast.next if fast:fast fast.next # 反转后半部分post self.reverse(slow) # 逐个比较pre head while (pre and post):if pre.val ! post.val:return False pre pre.next post post.next return True def reverse(self, node):if not node:return Noneelif not node.next:return node r self.reverse(node.next)node.next.next node node.next None return r10.复制复杂的链表
链表的每个节点都具有val, next, random属性。关键点是random如何获取——下标如何获取——借用list / 哈希表 class Solution:# 返回 RandomListNodedef Clone(self, pHead):if not pHead:return pHead dummy RandomListNode(-1)head RandomListNode(pHead.label)dummy.next head # 先复制原链表用两个数组分别记录新老链表的节点olist [pHead]nlist [head]p pHead.next while (p):head.next RandomListNode(p.label)head head.next nlist.append(head)olist.append(p)p p.next # 连接randomfor i in range(len(olist)):target olist[i].random if not target:continue idx olist.index(target)nlist[i].random nlist[idx]return dummy.next 更优的解法
class Solution {public Node copyRandomList(Node head) {if (head null) {return null;}ListNode nodes new ArrayList(); // 存放复制的节点MapNode, Integer mapping new HashMap(); // 用哈希表记录节点到下标的映射// 复制值并记录下标Node node head;int index 0;while (node ! null) {nodes.add(new Node(node.val));mapping.put(node, index);index;node node.next;}// 执行连接node head;for (int i 0; i nodes.size(); i) {// 1.连接randomNode temp nodes.get(i);if (node.random ! null) {int randomIndex mapping.get(node.random);temp.random nodes.get(randomIndex);}// 2.连接nextif (i nodes.size() - 1) {temp.next nodes.get(i 1);}node node.next;}return nodes.get(0);}
}11 链表加法 借助栈实现后端对齐处理最后一步的进位问题
class Solution:def addInList(self , head1 , head2 ):# write code here# 用栈s1, s2 [], []while head1:s1.append(head1)head1 head1.next while head2:s2.append(head2)head2 head2.next post None plus 0while (s1 and s2):n1, n2 s1.pop(), s2.pop()val n1.val n2.val plus plus 1 if val 10 else 0val - 10 if val 10 else 0node ListNode(val)node.next post post node if s1:while s1:n1 s1.pop()val n1.val plus plus 1 if val 10 else 0val - 10 if val 10 else 0node ListNode(val)node.next post post node elif s2:while s2:n2 s2.pop()val n2.val plus plus 1 if val 10 else 0val - 10 if val 10 else 0node ListNode(val)node.next post post nodeif plus 1:res ListNode(1)res.next post return res return post
