常见算法总结 - 链表篇
程序员文章站
2022-12-20 16:32:21
本文总结了常见高频的关于链表的算法考察。 1.如何找到链表的中间元素? 我们可以采用快慢指针的思想,使用步长为1的慢指针和步长为2的快指针,当快指针抵达链表末尾时,此时慢指针指向的即为中点位置。 我们还可以采用递归的方式,当递归到最末尾的时候,我们已经能知道链表的长度,此时当递归回去的时候,判断当前 ......
本文总结了常见高频的关于链表的算法考察。
1.如何找到链表的中间元素?
我们可以采用快慢指针的思想,使用步长为1的慢指针和步长为2的快指针,当快指针抵达链表末尾时,此时慢指针指向的即为中点位置。
public static linknode findmiddlebypointer(linknode node) { linknode slow = node; linknode fast = node; // 检测快指针是否可以安全移动 while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }
我们还可以采用递归的方式,当递归到最末尾的时候,我们已经能知道链表的长度,此时当递归回去的时候,判断当前递归层级等于链表长度一半的时候,即为链表的重点。
public static void findmiddlebyrecursion(linknode node, int recursionindex) { if (node.next != null) { findmiddlebyrecursion(node.next, recursionindex + 1); } else { middleindex = recursionindex % 2 == 0 ? recursionindex / 2 : recursionindex / 2 + 1; } if (middleindex == recursionindex) { system.out.println(node.value); } return; }
2.检测链表是否有环。
检测链表是否有环是非常常见的算法考察。常见的就是使用快慢指针,如果快慢指针有重合的时候,说明链表是有环的。
public static boolean isexistcircle(linknode node) { linknode slow = node; linknode fast = node; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }
3.如何列表反转(递归)
我们可以在递归回溯的时候,反向更改节点的指针。
public static void reverselinklistbyrecursion(linknode cur, linknode next) { if (next == null) { return; } reverselinklistbyrecursion(next, next.next); next.next = cur; cur.next = null; return; }
4.如何反转链表(非递归)
反转链表的非递归方式,我们可以采用三个指针,分别指向当前节点,下个节点,下下个节点,调整好下个节点的next指向后,继续利用下下个节点进行往后操作。
public static void reverselinklistbypointer(linknode node) { linknode cur = node; linknode next = node.next; linknode nextnext = null; cur.next = null; while (next != null) { nextnext = next.next; next.next = cur; cur = next; next = nextnext; } }
5.删除经过排序的链表中重复的节点。
通过在遍历中,判断当前的数字是否与之前的重复数字相同,如果相同的话,直接跳过,直到找到与之前重复数字不同时,将原先的指针跳过重复的节点,指向当前非重复数字节点。
public static void removeduplicatenode(linknode node) { if (node == null) { return; } linknode cur = node; linknode next = node.next; int dupicateval = node.value; while (next != null) { if (next.value == dupicateval) { next = next.next; continue; } dupicateval = next.value; cur.next = next; cur = next; next = next.next; } }
6.如何计算两个链表的代表数字之和。
将链表代表的数字进行相加即可,注意首位代表的是个位。3->1->5 代表513,5->9->2 代表295,最终计算结果为 8->0->8, 808。
public static linknode sumtwolinklist(linknode num1, linknode num2) { // 如果其中一个链表为空的,直接当做0处理,返回另外一个链表 if (num1 == null) { return num2; } if (num2 == null) { return num1; } linknode sum = new linknode(); // 保存头结点,如果计算完成后直接返回头结点 linknode head = sum; // 是否进位 boolean isover = false; // 当两个节点,其中一个存在时,即可进行累加 while (num1 != null || num2 != null) { // 默认初始化为0 int num1val = 0; int num2val = 0; if (num1 != null) { num1val = num1.value; } if (num2 != null) { num2val = num2.value; } // 如果进位的话 多加1 int singlesum = num1val + num2val + (isover == true ? 1 : 0); if (singlesum >= 10) { isover = true; singlesum = singlesum % 10; } else { isover = false; } sum.value = singlesum; // 移动指针 num1 = num1 != null ? num1.next : null; num2 = num2 != null ? num2.next : null; // 没有数字相加,直接结束 if (num1 == null && num2 == null) { break; } else { // 还有数字相加的话 提前生成下个数字 sum.next = new linknode(); sum = sum.next; } } return head; }
7.链表-奇数位升序偶数位降序-让链表变成升序
先将链表拆分成奇数的链表,和偶数的链表,然后翻转偶数的链表,在合并两个链表。
public class sortascdesclinklist { public static linknode oddlinklist = null; public static linknode evenlinklist = null; public static void main(string[] args) { // 初始化测试链表 linknode x1 = new linknode(1); linknode x2 = new linknode(10); linknode x3 = new linknode(2); linknode x4 = new linknode(9); linknode x5 = new linknode(3); linknode x6 = new linknode(8); linknode x7 = new linknode(4); linknode x8 = new linknode(7); linknode x9 = new linknode(5); linknode x10 = new linknode(6); x1.setnext(x2).setnext(x3).setnext(x4).setnext(x5).setnext(x6).setnext(x7).setnext(x8).setnext(x9).setnext(x10); // 先按奇数偶数位拆分链表 splitlist(x1); // 再反转链表 evenlinklist = reverselinklist(evenlinklist); // 再合并链表 mergelist(oddlinklist, evenlinklist); oddlinklist.printlist(); } /** * 拆分两个链表 * @param node */ public static void splitlist(linknode node) { oddlinklist = node; evenlinklist = node.next; linknode oddcur = node; linknode evencur = node.next; while (oddcur != null || evencur != null) { if (oddcur.next != null && oddcur.next.next != null) { oddcur.next = oddcur.next.next; oddcur = oddcur.next; }else { oddcur.next = null; oddcur = null; } if (evencur.next != null && evencur.next.next != null) { evencur.next = evencur.next.next; evencur = evencur.next; }else { evencur.next = null; evencur = null; } } } /** * 反转链表 * @param node * @return */ public static linknode reverselinklist(linknode node) { linknode cur = node; linknode next = node.next; linknode nextnext = null; cur.next = null; while (next != null) { nextnext = next.next; next.next = cur; cur = next; next = nextnext; } return cur; } /** * 合并两个链表 * @param oddlinklist * @param evenlinklist */ public static void mergelist(linknode oddlinklist, linknode evenlinklist) { linknode oddtail = oddlinklist; while (oddtail.next != null) { oddtail = oddtail.next; } oddtail.next = evenlinklist; } }
8.一个单向链表,删除倒数第n个数据。
准备两个指针,初始指向头结点,1号指针先走n步,然后2号指针开始走,当1号指针走到尾节点时,2号指针即为倒数第n个数据。
public static linknode findlastknumber(linknode node, int k) { linknode fast = node; linknode slow = node; for (int i = 0; i < k; i++) { // 如果fast为空的话,说明k超出范围 if (fast == null) { throw new runtimeexception("超出链表范围!"); } fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; }
笔者个人总结,如有错误之处望不吝指出。
本文转自我的个人博客:《coderv的进阶笔记》
欢迎加入java后端架构技术讨论群:1398880
我的公众号:coderv的进阶笔记,记录技术心得