前言
号外号外，笔者最近在系统整理一些 Java 后台方面的面试题和参考解答，有找工作需求的童鞋，欢迎关注我的 Github 仓库，如果觉得不错可以点个 star 关注 ：
- 1、awesome-java-interview
- 2、awesome-java-notes
链表相关的各种常用操作实现方法
经常刷 leetcode 的童鞋一定对单链表的各种骚操作不陌生，单链表可以玩出各种各样的骚操作，掌握单链表的各种常规操作一方面对于锻炼我们的编程思维和编程能力很有帮助，另一方面，面试的时候面试官也会经常问一些单链表相关的题目，可以让自己提前预热吧，对此感到不陌生。
总之，帮助很大就是了。废话不多说，以下主要根据自己平时刷题总结了一些高频的、常规的单链表操作题目，后续有时间还会不断补上，目前大体思路主要写在注释中，后续有时间再单独将思路整理出来。
1）单链表反转
2）链表中环的检测
3）返回链表中环的入口节点
4）两个有序链表的合并
5）链表中倒数第 n 个节点
6）求链表的中间节点
7）删除有序链表中的重复节点，只保留其中一个节点
8）删除有序链表中的所有重复节点 9）在 O(1)
时间内删除链表的节点
10）从尾到头打印链表
11）两个链表的第一个公共节点
package com.offers.leetcode.linkedlist;
import java.util.ArrayList;
import java.util.LinkedList;
public class LinkedListAlgo {
public static Node reverse(Node list) {
Node curr = list, pre = null;
while (curr != null) {
Node next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
public static boolean checkCircle(Node list) {
if (list == null) return false;
Node fast = list;
Node slow = list;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
public Node entryNodeOfList(Node head) {
if (head == null || head.next == null) {
return null;
}
Node fast = head;
Node slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
Node newSlow = head;
while (newSlow != slow) {
slow = slow.next;
newSlow = newSlow.next;
}
return slow;
}
}
return null;
}
public Node mergeTwoLists(Node l1, Node l2) {
Node soldier = new Node(0);
Node p = soldier;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) {
p.next = l1;
}
if (l2 != null) {
p.next = l2;
}
return soldier.next;
}
public static Node deleteLastKth(Node list, int k) {
if (list == null || k == 0) {
return null;
}
Node aheadNode = list;
Node behhindNode = list;
for (int i = 0; i < k - 1; i++) {
if (aheadNode.next == null) {
return null;
}
aheadNode = aheadNode.next;
}
while (aheadNode.next != null) {
aheadNode = aheadNode.next;
behhindNode = behhindNode.next;
}
return behhindNode;
}
public static Node findMiddleNode(Node list) {
if (list == null) return null;
Node fast = list;
Node slow = list;
while (fast.next != null & fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public Node deleteDulplicatesI(Node head) {
if (head == null || head.next == null) {
return head;
}
int val = head.data;
Node p = head;
while (p != null && p.next != null) {
if (p.next.data != val) {
val = p.next.data;
p = p.next;
} else {
Node n = p.next.next;
p.next = n;
}
}
return head;
}
public Node deleteDulplicatesII(Node head) {
if (head == null || head.next == null) {
return head;
}
Node soldier = new Node(head.data - 1);
soldier.next = head;
Node prev = soldier;
Node p = head;
while (p != null && p.next != null) {
if (p.data != p.next.data) {
prev = p;
p = p.next;
} else {
int val = p.data;
Node n = p.next.next;
while (n != null) {
if (n.data != val) {
break;
}
n = n.next;
}
prev.next = n;
p = n;
}
}
return soldier.next;
}
public void deleteNodeI(Node head, Node toBeDeleted) {
if (head == null || toBeDeleted == null) {
return;
}
if (head == toBeDeleted) {
head = head.next;
} else {
Node curr = head;
while (curr.next != null && curr.next != toBeDeleted) {
curr = curr.next;
}
if (curr.next == null) {
return;
}
curr.next = curr.next.next;
}
}
public void deleteNodeII(Node head, Node toBeDeleted) {
if (head == null || toBeDeleted == null) {
return;
}
if (toBeDeleted.next != null) {
Node p = toBeDeleted.next;
toBeDeleted.data = p.data;
toBeDeleted.next = p.next;
} else if (head == toBeDeleted) {
head = head.next;
} else {
Node curr = head;
while (curr.next != toBeDeleted) {
curr = curr.next;
}
curr.next = null;
}
}
public ArrayList<Integer> printListReversingly_Interatively(Node head) {
LinkedList<Integer> stack = new LinkedList<>();
Node pHead = head;
while (pHead != null) {
stack.push(pHead.data);
pHead = pHead.next;
}
return new ArrayList<>(stack);
}
private ArrayList<Integer> stack = new ArrayList<>();
public ArrayList<Integer> printListReversingly_Recursively(Node head) {
if (head != null) {
printListReversingly_Recursively(head.next);
stack.add(head.data);
}
return stack;
}
public Node findFirstCommonNode(Node list1, Node list2) {
int lengthOfList1 = getLengthOfList(list1);
int lengthOfList2 = getLengthOfList(list2);
int lengthDif = lengthOfList1 - lengthOfList2;
Node pListHeadLong = list1;
Node pListHeadShort = list2;
if (lengthOfList1 < lengthOfList2) {
pListHeadLong = list2;
pListHeadShort = list1;
lengthDif = lengthOfList2 - lengthOfList1;
}
for (int i = 0; i < lengthDif; i++) {
pListHeadLong = pListHeadLong.next;
}
while (pListHeadLong != null && pListHeadShort != null
|| (pListHeadLong != pListHeadShort)) {
pListHeadLong = pListHeadLong.next;
pListHeadShort = pListHeadShort.next;
}
Node firstCommonNode = pListHeadLong;
return firstCommonNode;
}
public int getLengthOfList(Node list) {
int lengthOfList = 0;
while (list != null) {
lengthOfList++;
list = list.next;
}
return lengthOfList;
}
public static Node createNode(int value) {
return new Node(value, null);
}
public static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
}
}
后记
如果你同我一样想要努力学好数据结构与算法、想要刷 LeetCode 和剑指 offer，欢迎关注我 GitHub 上的 LeetCode 题解：awesome-java-notes
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
