leetcode-hot-100-20230923

25. K 个一组翻转链表（Java实现）

/**
 * 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) {
        //思路：使用栈保存结点，先入栈，然后再出栈
        Stack<ListNode> st = new Stack();
        ListNode resultNode = new ListNode(0);
        ListNode prev = resultNode;

        while(true){
            //定义记录count个结点的变量
            ListNode tempNode = head;//设置一个指向head的变量
            int count = 0;

            while(tempNode != null && count < k){
                st.push(tempNode);
                tempNode = tempNode.next;
                count ++;
            }

            //表示当节点数量不满足k个时，直接break
            if(count < k){
                break;
            }

            //判断是否为空
            while(!st.empty()){
                //更新结果结点
                prev.next = new ListNode(st.peek().val);
                st.pop();//弹出栈顶结点
                prev = prev.next;
            }

            //更新prev.next结点
            prev.next = tempNode;

            //更新head
            head = tempNode;
        }

        return resultNode.next;

    }
}

138. 随机链表的复制（Java实现）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        //思路：实现链表的深拷贝
        //如果head结点等于null，直接返回null
        if(head == null){
            return head;
        }

        //指针指向head
        Node node = head;
        //使用map保存原始结点和新的结点
        Map<Node, Node> map = new HashMap<>();

        //遍历原始结点
        while(node != null){
            //创建和node.val相同的但是next和random等待初始化的结点
            Node tmp = new Node(node.val, null, null);
            map.put(node, tmp);
            //更新node指针
            node = node.next;
        }

        //node指向head
        node = head;
        while(node != null){
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }

        return map.get(head);

    }
}