内容简介：本文总结了常见高频的关于链表的算法考察。我们可以采用快慢指针的思想，使用步长为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;
}
笔者个人总结，如有错误之处望不吝指出。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Data Mining
Jiawei Han、Micheline Kamber、Jian Pei / Morgan Kaufmann / 2011-7-6 / USD 74.95
The increasing volume of data in modern business and science calls for more complex and sophisticated tools. Although advances in data mining technology have made extensive data collection much easier......一起来看看 《Data Mining》 这本书的介绍吧!
