文章目录
单链表反转
public class Test {
// 单链表遍历
public static void ergodic(Node curr){
while(curr != null){
System.out.print(curr.item);
curr = curr.next;
}
System.out.println();
}
// 单链表反转
public static Node reverse(Node list) {
// 将 list 标为 当前节点，并 初始化 前节点 pre 为 null
Node curr = list, pre = null;
// 当前节点为 null 时，则退出循环
while(curr != null){
// 将 当前节点 的 后节点 保存到 next
Node next = curr.next;
// 将 前节点pre 标记为 当前节点 的 后节点
curr.next = pre;
// 将 当前节点 标记为 前节点
pre = curr;
// 将 next 标记为 当前节点
curr = next;
}
return pre;
}
public static void main(String[] args) {
Node<Integer> node1 = new Node<>(1,null);
Node<Integer> node2 = new Node<>(2,node1);
Node<Integer> node3 = new Node<>(3,node2);
Node<Integer> node4 = new Node<>(4,node3);
ergodic(node4);
Node reverse = reverse(node4);
ergodic(reverse);
}
}
class Node<E> {
E item; // 当前元素的值
Node<E> next; // 指向下一个元素
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
链表中环的检测
快慢指针：
- 无终点长跑中，如果直线跑，快慢两个人的距离会越来越大，不可能相遇，
- 如果绕环跑，则快慢两个人必然相遇
public class Test {
// 检测环
public static boolean checkCircle(Node list) {
// 链表为 null 直接返回 false
if(list == null) return false;
// 初始化快慢指针
Node fast = list.next, slow = list;
// 如果无环，则 快指针 先到 尾结点
while(fast != null && fast.next != null){
// 快指针 一步 跑 两格
fast = fast.next.next;
// 慢指针 一步 跑 一格
slow = slow.next;
// 如果 快慢指针 相遇，则说明有环，如果无环，则 快指针 先到 尾结点
if(fast == slow) return true;
}
// 快指针 已经 到了 尾结点
return false;
}
public static void main(String[] args) {
Node<Integer> node1 = new Node<>(1,null);
Node<Integer> node2 = new Node<>(2,node1);
Node<Integer> node3 = new Node<>(3,node2);
Node<Integer> node4 = new Node<>(4,node3);
node1.next = node4;
System.out.println(checkCircle(node4));
}
}
class Node<E> {
E item; // 当前元素的值
Node<E> next; // 指向下一个元素
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
两个有序的链表合并
public class Test {
// 单链表遍历
public static void ergodic(Node curr){
while(curr != null){
System.out.print(curr.item);
curr = curr.next;
}
System.out.println();
}
// 有序链表合并 Leetcode 21
public static Node mergeTwoLists(Node<Integer> l1, Node<Integer> l2) {
// 利用哨兵结点简化实现难度
Node<Integer> soilder = new Node<>(0,null);
// 初始化当前节点
Node<Integer> curr = soilder;
// 只要有一个链表遍历结束，另一个链表的剩余节点都将大于新链表
while(l1 != null && l2 != null){
// 将较小值 作为 当前节点 的 后节点
if(l1.item < l2.item){
curr.next = l1;
// 更新 l1 节点
l1 = l1.next;
}else{
curr.next = l2;
l2 = l2.next;
}
// 更新当前节点
curr = curr.next;
}
// 将 未遍历完 的 链表 直接 放到 新链表 尾部
if(l1 != null) curr.next = l1;
if(l2 != null) curr.next = l2;
// 返回 不含 哨兵节点 的 链表
return soilder.next;
}
public static void main(String[] args) {
Node<Integer> node1 = new Node<>(7,null);
Node<Integer> node2 = new Node<>(5,node1);
Node<Integer> node3 = new Node<>(3,node2);
Node<Integer> node4 = new Node<>(1,node3);
Node<Integer> node5 = new Node<>(8,null);
Node<Integer> node6 = new Node<>(6,node5);
Node<Integer> node7 = new Node<>(4,node6);
Node<Integer> node8 = new Node<>(2,node7);
ergodic(mergeTwoLists(node4,node8));
}
}
class Node<E> {
E item; // 当前元素的值
Node<E> next; // 指向下一个元素
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
删除链表倒数第 n 个结点
public class Test {
// 删除倒数第K个结点
public static Node deleteLastKth(Node list, int k) {
Node fast = list;
int i = 1;
while (fast != null && i < k) {
fast = fast.next;
++i;
}
if (fast == null) return list;
Node slow = list, prev = null;
while (fast.next != null) {
fast = fast.next;
prev = slow;
slow = slow.next;
}
if (prev == null) {
list = list.next;
} else {
prev.next = prev.next.next;
}
return list;
}
public static void main(String[] args) {
Node<Integer> node1 = new Node<>(1,null);
Node<Integer> node2 = new Node<>(2,node1);
Node<Integer> node3 = new Node<>(3,node2);
Node<Integer> node4 = new Node<>(4,node3);
Node<Integer> node5 = new Node<>(5,node4);
Node<Integer> node6 = new Node<>(6,node5);
System.out.println(deleteLastKth(node6,5).next.item);
}
}
class Node<E> {
E item; // 当前元素的值
Node<E> next; // 指向下一个元素
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
求链表的中间结点
public class Test {
// 求中间结点
public static Node findMiddleNode(Node list) {
if(list == null) return null;
Node fast =list, slow = list;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public static void main(String[] args) {
Node<Integer> node1 = new Node<>(1,null);
Node<Integer> node2 = new Node<>(2,node1);
Node<Integer> node3 = new Node<>(3,node2);
Node<Integer> node4 = new Node<>(4,node3);
Node<Integer> node5 = new Node<>(5,node4);
Node<Integer> node6 = new Node<>(6,node5);
System.out.println(findMiddleNode(node6).item);
}
}
class Node<E> {
E item; // 当前元素的值
Node<E> next; // 指向下一个元素
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}