链表结束篇：链表的五种常见操作
2018-12-28 本文已影响0人
红酥手黄藤酒丶
链表结束篇：链表的五种常见操作
- 单链表翻转
- 检测一个链表中是否有环
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
更新一下 五、 的思路
规则界限就是：
快指针走的长度(链表长度 + null) = 快length = length + 1
快指针先走 n + 1
然后慢指针 和 快指针一起走，当快指针走到 快length 时
慢指针走到：
快length - (n + 1) = length + 1 - (n + 1) = length - n
第 (length - n) 位置就是倒数第(n + 1)个结点。
一、单链表翻转
在 判断回文串 这篇笔记中有详细记录，此处只列举代码了。
/**
* 链表的反转可以想象成摸石头过河那个游戏
* 两只脚配上三块砖头就可以前进了
* <p>
* 每次循环做的事：
* ①第一块砖头的next改变
* ②三块砖头前移一个位置
*
* @return 反转后的单链表
*/
public SingleLinked<E> reverse() {
Node<E> realHead = first;
//无结点
if (realHead == null) {
return this;
}
Node<E> temp = realHead.getNext();
//只有一个头结点
if (temp == null) {
return this;
}
Node<E> flag = temp.getNext();
//把realHead与其下一个结点的连接断开
realHead.setNext(null);
//一次循环，只改变一个结点的指针反转
//剩下就是temp flag 等引用的变化
while (flag != null) {
temp.setNext(realHead);
realHead = temp;
temp = flag;
flag = flag.getNext();
}
temp.setNext(realHead);
first = temp;
return this;
}
二、检测一个链表中是否有环
思路：使用快慢指针，快指针每次循环比慢指针多走一步，这样当快指针走到 null 时，慢指针走了一半， 若链表中有环（尾结点的后继指针指向了链表中的某一结点），那么 快指针 永远不会为 null，但是会出现 快指针与慢指针 指向同一结点的情况，以此来判断一个单链表是否有环。
image
画这个图好累。。。
public boolean hasCircle() {
Node<E> fast = first;
Node<E> slow = first;
while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
if (fast == slow) {
//说明有环，fast追到了 slow
return true;
}
}
return false;
}
三、两个有序的链表合并
思路：若两个链表都是升序链表。
取两个链表（A,B）的头结点比较谁小：将小的作为新链表的头结点。假设 B 小，接下来比较 B的头结点.next 与 A 的头结点谁小，小的作为新链表的头结点的 next。
image
可以使用递归解决此类问题：
import bean.Node;
import exception.CannotControlException;
import exception.UnorderedLinkedException;
/**
* @author : zyf
* @since : 2018-12-28 15:55
**/
public class SingleLinkedUtil {
private static final int ASC = 0;
private static final int DES = 1;
private static final int NULL_LINKED = 2;//表示空链表
private static final int UNORDERED = -1;
/**
* 判断链表是否有序
* @param linked
* @return 是升序还是降序
*/
public static int isOrderLinked(SingleLinked<Integer> linked){
Node<Integer> first = linked.getFirst();
if(first == null){
return NULL_LINKED;
}
Node<Integer> next = first.getNext();
//0 表示升序
//1 表示返序
int flag = UNORDERED;
while (next != null){
if(next.getT() >= first.getT()){
//大于 则 flag 为0
if(flag == UNORDERED){
//说明是第一次判断
flag = ASC;
}else {
if(flag != ASC){
//说明在循环中的某一次将 flag 的值改为 1 了
//说明不是一个有序链表
return UNORDERED;
}else {
first = next;
next = next.getNext();
}
}
}else {
//小于 则 flag 为 1
if(flag == -1){
flag = DES;
}else {
if(flag != DES){
return UNORDERED;
}else {
first = next;
next = next.getNext();
}
}
}
}
return flag;
}
public static SingleLinked<Integer> mergeOrderedLinked(SingleLinked<Integer> a,SingleLinked<Integer> b){
//先判断 a,b 是否有序
int aOrder = SingleLinkedUtil.isOrderLinked(a);
int bOrder = SingleLinkedUtil.isOrderLinked(b);
if(aOrder == NULL_LINKED){
return b;
}
if(bOrder == NULL_LINKED){
return a;
}
SingleLinked<Integer> result = new SingleLinked<Integer>();
if(aOrder != UNORDERED && bOrder != UNORDERED){
if(aOrder != bOrder){
//说明两者的排序方式不一样
throw new CannotControlException();
}else {
if(aOrder == ASC){
//说明两个链表都是升序
//通过递归的方式合并两个链表
result.addLast(mergeASC(a.getFirst(), b.getFirst()));
}else {
//说明两个链表都是降序
result.addLast(mergeDES(a.getFirst(), b.getFirst()));
}
}
}else {
throw new UnorderedLinkedException();
}
return result;
}
/**
* 合并升序链表
* @param nodeA
* @param nodeB
* @return
*/
private static Node<Integer> mergeASC(Node<Integer> nodeA,Node<Integer> nodeB){
Node<Integer> result;
if(nodeA == null){
return nodeB;
}
if(nodeB == null){
return nodeA;
}
if(nodeA.getT() < nodeB.getT()){
result = nodeA;
result.setNext(mergeASC(nodeA.getNext(),nodeB));
}else {
result = nodeB;
result.setNext(mergeASC(nodeA,nodeB.getNext()));
}
return result;
}
/**
* 合并降序链表
* @param nodeA
* @param nodeB
* @return
*/
private static Node<Integer> mergeDES(Node<Integer> nodeA,Node<Integer> nodeB){
Node<Integer> result;
if(nodeA == null){
return nodeB;
}
if(nodeB == null){
return nodeA;
}
if(nodeA.getT() > nodeB.getT()){
result = nodeA;
result.setNext(mergeDES(nodeA.getNext(),nodeB));
}else {
result = nodeB;
result.setNext(mergeDES(nodeA,nodeB.getNext()));
}
return result;
}
}
四、删除单链表倒数第 n 个结点
这个好难，网上找到的答案能看懂，知道会得到正确的结果，但是如何表述思考过程好难。
image
public void removeAtFromEnd2(int n) {
if (n <= 0) {
throw new UnsupportedOperationException("n必须大于0");
}
int length = 0;
Node<E> temp = this.first;
while (temp != null) {
temp = temp.getNext();
length++;
}
if(n > length){
throw new LinkedOutOfBoundsException();
}
int target = length - n;
Node<E> again = this.first;
if(target == 0){
//要移除第一个
this.first = again.getNext();
}
while (target > 1) {
again = again.getNext();
target--;
}
again.setNext(again.getNext().getNext());
}
五、删除单链表倒数第 n 个结点（使用快慢指针的方式解决问题）
image
/**
* 为什么最后从 0 开始移动的？
* 自己可以运行测试一下，如果要删除的是链表的头结点
* 那么从 头结点前开始移动，代码会更优化
*
* @param n
*/
public void removeAtFromEnd(int n) {
if (n <= 0) {
throw new UnsupportedOperationException("n必须大于0");
}
Node<E> beforeFirst = new Node<>();
beforeFirst.setNext(first);
//现在快慢指针都在 0 位置呢（如果假设头结点为 1 ）
Node<E> fast = beforeFirst;
Node<E> slow = beforeFirst;
//开始移动 fast 直到到达 size - n 的位置
while (fast != null && n > -1) {
fast = fast.getNext();
n--;
}
if (n > -1) {
//说明要删除的位置超过了链表的长度
throw new LinkedOutOfBoundsException();
}
//当 fast 处于 n 的位置的时候
//再让 slow 与 fast 一起移动
//这样当 fast 移动到链表尾部 fast==null 为 true 时
//slow 正好移动到 size - n 的位置
while (fast != null) {
fast = fast.getNext();
slow = slow.getNext();
}
slow.setNext(slow.getNext().getNext());
}
六、求链表的中间结点
这个和第 二 道题很像，都是使用快慢指针来解决问题。
快指针从头结点每次循环走两步。
慢指针从头结点每次循环走一步。
当快指针走到null时，慢指针刚好走到链表中间结点。
若链表长度为奇数：慢指针是中间结点。
若链表长度为偶数：慢指针是上中结点，慢指针.next 是下中结点。
[1,2,3,4,5,6,7,8] ：上中结点：4 下中结点：5
/**
* 使用快慢指针即可拿到中间结点
* 快指针比慢指针多走一步即可
*
* @return
*/
public Node<E> getMiddleNode() {
if (first == null) {
throw new EmptyLinkedException();
}
Node<E> fast = first;
Node<E> slow = first;
while (fast.getNext() != null && fast.getNext().getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
}
return slow;
}
