单链表（Java）

1. 单链表结构

每一个节点之间通过next指针指向下一个节点

class TreeNode {
    public int val;
    public TreeNode next;

    public TreeNode () {
    }

    public TreeNode (int val) {
        this.val = val;
    }
}

2. 单链表的技巧

2.1 翻转链表

/**
     * 翻转链表
     *
     * @return 放回新链表的头节点
     */
public static TreeNode reverseLinked(TreeNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 创建辅助节点 进行移动
    TreeNode curNode = head;
    TreeNode curNextNode = head.next;
    curNode.next = null;
    while (curNextNode != null) {
        TreeNode temp = curNextNode.next;
        curNextNode.next = curNode;
        curNode = curNextNode;
        curNextNode = temp;
    }
    return curNode;
}

2.1 快慢指针

作用1：找到单链表的中间的位置

/**
 * @author zyq
 * @version 1.0
 */
public class LinkedDemo {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        System.out.println(getMiddenLinked(node1).val);
    }

    public static Node getMiddenLinked(Node head) {
        // base case
        // 使用快慢指针的方式解决问题
        if (head == null) {
            return null;
        }
        // 设置快慢指针
        // 这里设置快指针走两步   慢指针走一步
        Node slow = head;
        Node fast = head;
        while (slow != null && fast.next != null) {
            // 当是偶数的时候 选择中间靠前的一个
            if (fast.next.next  == null) {
                break;
            }
            // 慢指针走一步
            slow = slow.next;
            // 快指针走两步
            fast = fast.next.next;
        }
        return slow;
    }

    public static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node() {
        }
    }
}

作用2：判断单链表是否为环，快指针走两步、慢指针走一步，如果快指针走完了快慢指针还没有进行相遇，说明这个单链表不构成环。
在构成环的前提下，将这个快指针回到链表的初始的位置，再快慢指针都以一步的方式进行移动，最后相遇的地方就是交点位置。

/*
     * 1、如果快指针走完了还没有快慢指针相遇，什么这个单链表不是环状的单链表
     *
     * 2、如果快慢指针进行了相遇，说明是单链表，
     * 这个时候将快指针回到开始的地方，慢指针不动，这个时候同时走一步的方式，
     * 当快慢指针再次相遇的时候，这个位置就是第一个相交的位置
     */
public static Node getLoopNode(Node head) {
    // 排除额外的情况
    if (head == null || head.next == null || head.next.next == null) return null;
    // 设置快慢指针 都先动一步
    Node fast = head.next.next;
    Node slow = head.next;
    boolean judgeLoop = false;
    // 找到相遇的位置
    while (fast != null && fast.next != null) {
        // 不想等 进行移动
        if (slow == fast) {
            // 相遇 说明是环
            judgeLoop = true;
            break;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    // 不是环
    if (!judgeLoop) return null;
    // 是环 将快指针回到开始的位置
    fast = head;
    // 一起走一步到相遇的位置
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

3. 算法题

3.1 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

package com.sort.S2022_10_12;

/**
 * @author zyq
 * @version 1.0
 */
public class RemoveNthFromEnd {
    /**
     * 第一步将链表的长度求出来，找到倒数第n个的数为多少
     * <p>
     * 第二步将这个节点进行删除就可以
     *
     * @param head 头节点
     * @param n    倒数第几个
     * @return 头节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        // 1 计算链表的长度
        int num = 0;
        ListNode temp = head;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        // 总共长度为 num 的长度
        int count = num - n;
        if (count == 0) {
            // 说明是第一个
            head = head.next;
            return head;
        }
        // 计算出链表的长度
        temp = head;
        int tempCount = 1;
        while (temp != null) {
            if (tempCount++ < count) {
                temp = temp.next;
            } else {
                temp.next = temp.next.next;
                break;
            }
        }
        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

思路二

1、将链表进行反转

2、删除指定位置的节点皆可

//1、将链表进行反转
//2、删除指定位置的节点皆可
public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
        return null;
    }
    head = reserveLinked(head);
    ListNode temp = head;
    if (n == 1) {
        head = head.next;
        return reserveLinked(head);
    }
    // 计数
    int count = 0;
    while (temp != null) {
        count++;
        if (count == n - 1) {
            temp.next = temp.next.next;
        }
        temp = temp.next;
    }
    return reserveLinked(head);
}

// 翻转链表
public static ListNode reserveLinked(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode curNode = head;
    ListNode curNextNode = head.next;
    curNode.next = null;
    while (curNextNode != null) {
        ListNode temp = curNextNode.next;
        curNextNode.next = curNode;
        curNode = curNextNode;
        curNextNode = temp;
    }
    return curNode;
}

思路三

1、使用双指针的方式进行解决，先要一个指针走n步

2、再一起向后走，当快的那一个走到最后的时候，慢的那个就是在倒数n的位置

// 1、使用双指针的方式进行解决，先要一个指针走n步
// 2、再一起向后走，当快的那一个走到最后的时候，慢的那个就是在倒数n的位置
public static ListNode removeNthFromEnd3(ListNode head, int n) {g
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    // 准备一个阈值的方式
    ListNode slow = new ListNode(0, head);
    ListNode temp = slow;
    // 将fast向后走n步
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    // 再将fast和slow一起向后走 一直走到fast不可以走了
    while (fast != null) {
        fast = fast.next;
        temp = temp.next;
    }
    // 将slow后面的那个进行删除
    temp.next = temp.next.next;
    return slow.next;
}

3.2 将一个链表按某值划分成左边小，中间相等，右边大的情况

思路一：

1、将链表转成对应的数组

2、使用快排的方式进行排序好，再将数组转成对应的链表

/**
     * 1、将链表转成对应的数组
     * 2、使用快排的方式进行排序好，再将数组转成对应的链表
     *
     * @return 排序好的链表
     */
public static ListNode linkedSort(ListNode head, int pivot) {
    // 对应的数组的值
    int[] arr = convertArr(head);
    // 进行一个partition
    partition(arr, 0, arr.length - 1, pivot);
    // 转成对应的链表的结构
    return convertLinked(arr);
}

// 将单链表转成对应的数组
public static int[] convertArr(ListNode head) {
    List<Integer> list = new ArrayList<>();
    ListNode temp = head;
    while (temp != null) {
        list.add(temp.val);
        temp = temp.next;
    }
    int[] arr = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        arr[i] = list.get(i);
    }
    return arr;
}

// 将数组转成对应的单链表
public static ListNode convertLinked(int[] arr) {
    ListNode head = new ListNode(0);
    ListNode temp = head;
    for (int i : arr) {
        ListNode listNode = new ListNode(i);
        temp.next = listNode;
        temp = listNode;
    }
    return head.next;
}

public static int[] partition(int[] arr, int left, int right, int pivot) {
    // 确定小于的区域
    int minZone = left - 1;
    // 确定大于的区域
    int maxZone = right + 1;
    // 进行移动的指针
    int temp = left;
    while (temp < maxZone) {
        if (arr[temp] < pivot) {
            // 小于 temp向后移动 minZone向后移动 进行交换
            swap(arr, ++minZone, temp++);
        } else if (arr[temp] > pivot) {
            swap(arr, --maxZone, temp);
        } else {
            temp++;
        }
    }
    return arr;
}

public static void swap(int[] arr, int left, int right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

思路二

使用空间复杂度为O(1)的级别进行解决

和数组的partition类似，准备6个变量，左边的头，左边的尾，中间的头，中间的尾，右边的头，右边的尾

// 和数组的partition类似，准备6个变量，左边的头，左边的尾，中间的头，中间的尾，右边的头，右边的尾
public static ListNode linkedSort2(ListNode head, int pivot) {
    // 左边的头
    ListNode lH = null;
    // 左边的尾
    ListNode lT = null;
    // 中间的头
    ListNode eH = null;
    // 中间的尾
    ListNode eT = null;
    // 右边的头
    ListNode rH = null;
    // 右边的尾
    ListNode rT = null;
    ListNode next;
    ListNode temp = head;
    while (temp != null) {
        // 记录下一个节点
        next = temp.next;
        temp.next = null;
        if (temp.val < pivot) {
            if (lH == null) {
                lH = temp;
            } else {
                lT.next = temp;
            }
            lT = temp;
        } else if (temp.val == pivot) {
            if (eH == null) {
                eH = temp;
            } else {
                eT.next = temp;
            }
            eT = temp;
        } else {
            if (rH == null) {
                rH = temp;
            } else {
                rT.next = temp;
            }
            rT = temp;
        }
        temp = next;
    }
    // 是否有些情况没有  有小于区域
    if (lT != null) {
        lT.next = eH;
        eT = eT != null ? eT : lT;
    }
    // 等于部分有
    if (eT != null) {
        eT.next = rH;
    }
    // 如果上面都没有
    return lH != null ? lH : (eH != null ? eH : lH);
}

3.3 复制含随机指针节点的链表

使用Hash表的方式进行一一对应进行克隆

// 使用Hash表的方式进行一一对应进行克隆
public static Node hashCopyLinked(Node head) {
    Map<Node, Node> map = new HashMap<>();
    Node temp = head;
    // 将所有的节点进行复制 放入到map中
    while (temp != null) {
        map.put(temp, new Node(temp.val));
        temp = temp.next;
    }
    temp = head;
    while (temp != null) {
        map.get(temp).next = map.get(temp.next);
        map.get(temp).rand = map.get(temp.rand);
        temp = temp.next;
    }
    return map.get(head);
}

思路二

不使用额外的空间做这个题目

1、将所有的节点进行复制，放到复制的节点的后面

2、然后两个两个进行处理，最后将这个链表分成两个链表

// 1、将所有的节点进行复制，放到复制的节点的后面
//2、然后两个两个进行处理，最后将这个链表分成两个链表
public static Node copyLinked(Node head) {
    Node temp = head;
    while (temp != null) {
        // 复制一个节点
        Node node = new Node(temp.val);
        // 放到前节点的后面
        Node tempNode = temp.next;
        temp.next = node;
        node.next = tempNode;
        temp = node.next;
    }
    // 然后两个两个进行处理
    temp = head;
    while (temp != null && temp.next != null) {
        if (temp.rand == null) {
            temp.next.rand = null;
        } else {
            temp.next.rand = temp.rand.next;
        }
        temp = temp.next.next;
    }
    // 分离
    temp = head;
    Node res = head.next;
    Node curNode;
    Node next;
    while (temp != null) {
        next = temp.next.next;
        curNode = temp.next;
        temp.next = next;
        curNode.next = next != null ? next.next : null;
        temp = next;
    }
    return res;
}