Java算法 - 《算法》

一、链表

一、链表

1、回文链表

判断一个链表是否为回文结构：给定一个链表的头结点head，请判断该链表是否回文结构，例如：1 -> 2 ->
1,返回true。1 ->2 ->3, 返回false。

算法一：遍历链表，将node加入栈中，再遍历栈，和原始链表比对，如果相等，说明是回文链表。

算法一增强版：

快慢指针：当快指针走到结尾的时候，慢指针走到中点的下一个位置
将慢指针和之后的节点压栈
弹栈，和链表的前半部分比较

算法二：

快慢指针：当快指针走到结尾的时候，慢指针走到中点
逆序从慢指针开始的后半部分
新建两个指针从头和尾遍历，到终点node为止
如果都相等，返回true，否则返回false
最后再将后半部分恢复回来


public class Palindrome {
    public static void main(String[] args) {
        Node head = linkGenerator(new int[]{1,2,3,4,5,5,4,3,2,1});
        System.out.println(head);
        System.out.println(isPalindrome3(head));
    }
    //空间复杂度为n
    public static boolean isPalindrome1(Node head){
        Stack<Integer> stack = new Stack<>();
        Node pointer = head;
        while (pointer!=null){
            stack.push(pointer.val);
            pointer = pointer.next;
        }
        pointer = head;
        while (!stack.isEmpty()){
            if (stack.pop()!=pointer.val){
                return false;
            }
            pointer = pointer.next;
        }
        return true;
    }
    //空间复杂度为n/2
    public static boolean isPalindrome2(Node head){
        if (head == null || head.next == null){
            return true;
        }
        Node slow = head.next;//注意这里慢指针的初始位置
        Node fast = head;
        //当循环终止时，fast在最后一位（奇数），或者在倒数第二位（偶数）
        //slow在中间位置的下一位（奇数）1->2->3->(2)->1，或者在中间相等两数的第二个数（偶数）1->2->3->(3)->2->1
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //将此时从slow开始的链表压栈
        Stack<Integer> stack = new Stack<>();
        while (slow!=null){
            stack.push(slow.val);
            slow = slow.next;
        }
        while(!stack.isEmpty()){
            if (head.val != stack.pop()){
                return false;
            }
            head = head.next;
        }
        return true;
    }
    //空间复杂度为O(1)
    public static boolean isPalindrome3(Node head){
        if (head == null || head.next == null){
            return true;
        }
        Node n1 = head;//慢指针
        Node n2 = head;//快指针
        //慢指针移动到中点，或者中间偏左的位置（偶数）
        while(n2.next!=null&&n2.next.next!=null){
            n1 = n1.next;
            n2 = n2.next.next;
        }
        //开始反转后半部分的链表
        n2 = n1.next;
        n1.next = null;//mid.next = null
        Node n3 = null;
        while(n2!=null){
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        //两个节点分别从两端遍历，查看每个节点的相等情况
        n3 = n1;
        n2 = head;
        boolean res = true;
        while (n1!=null&&n2!=null){
            if (n1.val!=n2.val){
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        //再将后半部分的链表反转回来
        n1 = n3.next;
        n3.next = null;
        while(n1!=null){
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }
}

2、链表节点的移动

要求：给定一个链表和一个数字，将比这个数字小的节点放在左边，比这个数字大的节点放在右边，和这个数字相等的节点放在中间
时间复杂度为O(N)，空间复杂度为O(1)

算法一：
通过定义6个结点分别表示每一段链表的头结点和尾节点，最后将生成的链表段连接。

public class Code02_SmallerEqualBigger {
    public static class Node{
        public int value;
        public Node next;
        public Node(int value) {
            this.value = value;
        }
    }
    /**
     * 分成3个链表实现三块区域的局部链表在连接
     *
     */
    public static Node listPartition(Node head, int pivot){
        //创建6个参数
        Node sH = null; // small head
        Node sT = null; // small Tail
        Node eH = null; // equal head
        Node eT = null; // equal Tail
        Node mH = null; // big head
        Node mT = null; // big Tail
        Node next = null; // save next node
        while (head != null){
            next = head.next;
            head.next = next;
            if (head.value < pivot){
                if(sH == null){
                    sH = head;
                    sT = head;
                }else {
                    sT.next = head;
                    sT = head;
                }
            }else if (head.value == pivot){
                if(eH == null){
                    eH = head;
                    eT = head;
                }else {
                    eT.next = head;
                    eT = head;
                }
            }else {
                if(mH == null){
                    mH = head;
                    mT = head;
                }else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }
//        如果有小于区域
        if (sT != null){
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        //如果有小于和等于区域
        if(eT != null){
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }

3、链表的Copy

题目：在链表的结点中，除了val，next之外，还有一个类型为Node的随机指针，它可能指向链表中的任何一个节点，也可能指向null。

1、算法一：
使用HashMap ：

将原链表中的节点作为key，将copy后的节点作为value，放入HashMap中。
重建新的链表
通过映射关系，重建rand关系：1’和 2’之间的关系可以通过1和2之间的关系得到

需要额外空间

代码：


public class DeepCopy {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.rand = head;
        head.next.next.rand = null;
    }
    //需要额外的存储空间
    public static Node copyListWithRand1(Node head){
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }
}
class Node{
    int val;
    Node next;
    Node rand;
    public Node(int val) {
        this.val = val;
    }
}

算法2：不用HashMap
空间复杂度为O(1)

通过第一次遍历，将原来的链表：

20201202212229667 (1).jpg 每个copy节点都连接在原节点的后面

当确定rand或者next关系的时候，首先通过原来链表的rand关系找到（1找到2），因为2’就在2的下一位，所以1’可以直接找到2’（通过这种结构关系，巧妙地避免了HashMap的使用）
最后，分离混合的链表（在这里面重新确定next关系）

//不需要额外的存储空间
    public static Node copyListWithRand2(Node head){
        Node cur = head;
        Node next = null;
        //构造出 1 -> 1 -> 2 -> 2 -> 3 -> 3 这种结构
        while(cur!=null){
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        //设置 “复制Node”的rand指针
        while(cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand == null? null:cur.rand.next;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        //分离混合在一起的链表
        while(cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next==null?null:next.next;
            cur = next;
        }
        return res;
    }

4、合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
方法一：使用分治思想来实现合并，将其分为多个双链表的合并；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 如果没有链表则返回null
        if (lists.length == 0) return null;
        return mergeSort(lists,0,lists.length -1);
    }

    public ListNode mergeSort(ListNode[] lists,int left,int right){
        // 停止递  实现归
        if (left == right) return lists[left];
        // 二分法来实现归并
        int mid = (left + right)/2;
        ListNode l1 = mergeSort(lists,left,mid);
        ListNode l2 = mergeSort(lists,mid + 1, right);
        return merge(l1,l2);    
    }

    // 下面的方法为两个链表实现合并
    public ListNode merge(ListNode l1,ListNode l2){

        ListNode preNode = new ListNode(0);
        ListNode list = preNode;
        while (l1 != null && l2 != null){
            // 比较大小合并
            if (l1.val <= l2.val){
                list.next = l1;
                l1 = l1.next;
            }else if(l1.val > l2.val){
                list.next = l2;
                l2 = l2.next;
            }

            list = list.next;
        }
        // 将剩余的节点连接（因为已经是升序了）
        list.next = l1 == null ? l2:l1;
        return preNode.next;
    }
}

5、两两交换链表中的节点

将链表中的节点两两交换
方法一：使用双指针实现节点的交换

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = temp;
        while (pre.next != null && pre.next.next != null){
            // 保存需要交换的两个节点
            ListNode first = pre.next;
            ListNode second = pre.next.next;
            // pre为上一个交换的 的first  相当于first为上一个节点的结尾节点
            // 1->2->3->4->5  交换一轮后pre-> 2->1->3->4->5  1为first  pre保存当前节点
            pre.next = second;
            first.next = second.next;
            second.next = first;
            // 下一个循环
            pre = first;
        }
        // 返回自己定义的链表
        return dummy.next;
    }
}

方法二：使用递归解法

class Solution {
    public ListNode swapPairs(ListNode head) {
        //递归的终止条件
        if(head==null || head.next==null) {
            return head;
        }
        //假设链表是 1->2->3->4
        //这句就先保存节点2
        ListNode tmp = head.next;
        //继续递归，处理节点3->4
        //当递归结束返回后，就变成了4->3
        //于是head节点就指向了4，变成1->4->3
        head.next = swapPairs(tmp.next);
        //将2节点指向1
        tmp.next = head;
        return tmp;
    }
}

6、实现k个结点逆转

和5的解法相似将一个链表循环k个结点为一个链表来逆转再连接

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        // 创建一个头头结点 dummy -> head -> 
        dummy.next = head; 

        ListNode pre = dummy;
        ListNode end = dummy;

        // 判断是否需要进行循环
        while (end.next != null){
            //通过 k 的长度获取每个循环的 最后一个节点
            for(int i = 0;i<k && end != null;i++) end = end.next;
            // 如果当前的end为null则退出循环
            if (end == null) break;
            // start 存 第一个位置  next 存 下一个循环的第一个位置
            ListNode start = pre.next;
            ListNode next = end.next;
            //断开当前循环
            end.next = null;

            // 逆转链表 dummy -> 1 -> 2 逆转成 dummy -> 2 -> 1  pre为每个循环前一个节点 相当于dummy
            pre.next = reverse(start);
            // 将 1 -> 的next  为next
            start.next = next;

            // 这个是将下一个循环准备
            pre = start;
            end = start;
        }
        return dummy.next;
    }

    public ListNode reverse(ListNode temp){
        ListNode left = temp;
        ListNode pre = null;
        while (left != null){
            // 将next放到第一位
            ListNode next = left.next;

            // 第一个的next指向null
            left.next = pre;
            // 移动
            pre = left;
            // 循环到下一个
            left = next;
        }
        return pre;
    }
}

7、旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
解法：将链表首尾连接再获取链表长度通过余数循环链表找到该链表断开首尾链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode temp = head;
        ListNode left = head;
        ListNode right = head;
        if (head == null) return null;
        // 计算链表长度
        ListNode count = head;
        int n = 1;
        while (count.next != null){
            count = count.next;
            n++;
        }
        // 获取余数 只跑一圈以内
        k = k % n;
        // 判断
        if (k <=0 || head.next == null) return head;
        // 双指针 找到k的位置
        for (int i = 0; i<k && right.next != null;i++){
            right = right.next;
        }
        // 将链表成环
        while (right.next != null){
            left = left.next;
            // 为k的位置
            right = right.next;
        }
        ListNode resNode = left.next;
        right.next = temp;
        left.next = null;
        return resNode;
    }
}

8、删除排序链表的重复元素

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        // 当前节点和下一节点的比较
        if (head.val != head.next.val){
            head.next = deleteDuplicates(head.next);
            return head;
        }else{
            // 查找重复的个数  找到下下个 
            // 1->2->3->3->4->4->5
            // 当前节点为第三个 3  比较当前节点和后一个节点 如果相等 则获取4 然后返回返回4的当前节点
            ListNode notDup = head.next.next;
            while (notDup != null && notDup.val == head.val){
                notDup = notDup.next;
            }
            return deleteDuplicates(notDup);
        }
    }
}

删除重复元素只保存一个元素

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 判断
        if (head == null) return null;
        // 代替
        ListNode right = head;
        // 判断是否为空
        // 保存  一个节点
        // 1 -> 1 -> 2-> 3-> 3
        // 比较 第1个和第二个是否相等 如果相等 则删除下一个
        while (right.next != null){
            if (right.val == right.next.val){
                right.next = right.next.next;
            }else{
                right = right.next;
            }
        }
        return head;
    }
}

9、分隔链表

给你一个链表的头节点 head 和一个特定值_ _x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。
这个算法的解法思路：将x的大小分为2个链表再连接起来两个dummy 然后再首尾连接

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode pre = dummy1;
        ListNode last = dummy2;

        while (head != null){
            if (head.val < x){
                pre.next = head;
                pre = pre.next;
            }else{
                last.next = head;
                last = last.next;
            }
            head = head.next;
        }
        last.next = null;
        pre.next = dummy2.next;
        return dummy1.next;

    }
}