首页 > 其他分享 >[左神面试指南] 链表[上]篇

[左神面试指南] 链表[上]篇

时间:2023-11-08 12:44:52浏览次数:41  
标签:head ListNode int 左神 next 链表 面试 tail public

CD48 打印两个有序链表的公共部分

/* 归并 */
public class CD48_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }


    public static ArrayList<Integer> solution(ListNode l1, ListNode l2)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
                l1 = l1.next;
            else if (l1.val > l2.val)
                l2 = l2.next;
            else
            {
                ans.add(l1.val);
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, M;
        N = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = in.nextInt();
        M = in.nextInt();
        int[] l2 = new int[M];
        for (int i = 0; i < M; i++)
            l2[i] = in.nextInt();
        ArrayList<Integer> res = solution(ListNode.createSingleList(l1)[0], ListNode.createSingleList(l2)[0]);
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CD49 在单链表和双链表中删除倒数第 K 个节点

/* 双指针 */
public class CD49_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head, int K)
    {
        ListNode pre = head, last = head;
        while (K-- > 0)
            last = last.next;
        if (last == null) return head.next;
        while (last.next != null)
        {
            pre = pre.next;
            last = last.next;
        }
        pre.next = pre.next.next;
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt(), K = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0], K);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

/* 单指针 */
public class CD49_2
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }


    public static ListNode solution(ListNode head, int K)
    {
        ListNode pre = head;
        while (pre != null)
        {
            K--;
            pre = pre.next;
        }
        pre = head;
        if (K == 0) head = head.next;
        else if (K < 0)
        {
            while (++K < 0)
                pre = pre.next;
            pre.next = pre.next.next;
        }
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt(), K = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0], K);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

CD106 删除链表的中间节点和 a/b 处的节点

/* 模拟 */
public class CD106_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }


    public static ListNode solution(ListNode head, int K)
    {
        ListNode pre = head;
        if (K == 1) return head.next;
        K--;
        while (--K > 0)
            pre = pre.next;
        pre.next = pre.next.next;
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt(), K = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0], K);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

/* 快慢双指针(删除中间节点) */
public class CD106_2
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head)
    {
        if (head == null || head.next == null)
            return head;
        if (head.next.next == null)
            return head.next;
        ListNode pre = head, cur = head.next.next;
        while (cur.next != null && cur.next.next != null)
        {
            pre = pre.next;
            cur = cur.next.next;
        }
        pre.next = pre.next.next;
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0]);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

CD107 反转单向和双向链表

/* 模拟 */
public class CD107_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static class DoubleListNode
    {
        public int val;
        public DoubleListNode next = null;
        public DoubleListNode prev = null;

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

        public static DoubleListNode[] createDoubleList(int[] nums)
        {
            DoubleListNode head = new DoubleListNode(-1), tail = head;
            for (int num : nums)
            {
                DoubleListNode temp = new DoubleListNode(num);
                tail.next = temp;
                temp.prev = tail;
                tail = temp;
            }
            head.next.prev = null;
            return new DoubleListNode[]{head.next, tail};
        }
    }


    public static ListNode solutionSingle(ListNode head)
    {
        ListNode temp, tail = head.next;
        head.next = null;
        while (tail != null)
        {
            temp = tail.next;
            tail.next = head;
            head = tail;
            tail = temp;
        }
        return head;
    }

    public static DoubleListNode solutionDouble(DoubleListNode head)
    {
        DoubleListNode temp, tail = head.next;
        head.next = null;
        while (tail != null)
        {
            temp = tail.next;
            tail.next = head;
            head.prev = tail;
            head = tail;
            tail = temp;
        }
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, M;
        N = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = in.nextInt();
        ListNode res1 = solutionSingle(ListNode.createSingleList(l1)[0]);
        while (res1 != null)
        {
            out.print(res1.val + (res1.next == null ? "" : " "));
            res1 = res1.next;
        }
        out.println();

        M = in.nextInt();
        int[] l2 = new int[M];
        for (int i = 0; i < M; i++)
            l2[i] = in.nextInt();
        DoubleListNode res2 = solutionDouble(DoubleListNode.createDoubleList(l2)[0]);
        while (res2 != null)
        {
            out.print(res2.val + (res2.next == null ? "" : " "));
            res2 = res2.next;
        }
        out.flush();
    }
}

CD108 反转部分单向链表

/* 模拟 */
public class CD108_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head, int L, int R)
    {
        int cnt = 0;
        ListNode fakeHead = new ListNode(-1), pre = fakeHead, revStart = null, revEnd = null, tail = null, temp;
        fakeHead.next = head;
        while (head != null)
        {
            cnt++;
            if (cnt == L)
            {
                tail = pre;
                revStart = head;
            }
            if (cnt == R)
            {
                revEnd = head.next;
                head.next = null;
                break;
            }
            pre = pre.next;
            head = head.next;
        }
        temp = revStart;
        ListNode reverse = reverse(revStart);
        temp.next = revEnd;
        tail.next = reverse;
        return fakeHead.next;
    }

    public static ListNode reverse(ListNode head)
    {
        ListNode temp, tail = head.next;
        head.next = null;
        while (tail != null)
        {
            temp = tail.next;
            tail.next = head;
            head = tail;
            tail = temp;
        }
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, L, R;
        N = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = in.nextInt();
        L = in.nextInt();
        R = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l1)[0], L, R);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

CD109 环形单链表的约瑟夫问题

/* 模拟 */
public class CD109_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            tail.next = head.next;
            return new ListNode[]{head.next, tail};
        }
    }

    public static void solution(ListNode head, int M)
    {
        ListNode pre, temp = head;
        while (temp.next != head)
            temp = temp.next;
        pre = temp;
        int cnt = 0;
        while (pre.next != pre)
        {
            cnt++;
            if (cnt == M)
            {
                cnt = 0;
                pre.next = head.next;
                head = pre.next;
                continue;
            }
            pre = pre.next;
            head = head.next;
        }
        System.out.println(pre.next.val);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, M;
        N = in.nextInt();
        M = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = i + 1;
        solution(ListNode.createSingleList(l1)[0], M);
    }
}

CD110 环形单链表的约瑟夫问题(进阶)

/* 约瑟夫算法 */
public class CD110_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            tail.next = head.next;
            return new ListNode[]{head.next, tail};
        }
    }

    public static void solution(ListNode head, int M)
    {
        int len = 1, th;
        ListNode temp = head;
        while (temp.next != head)
        {
            len++;
            temp = temp.next;
        }
        th = LastRemaining_Solution(len, M);
        while (th-- > 0)
            head = head.next;
        System.out.println(head.val);
    }

    public static int LastRemaining_Solution(int n, int m)
    {
        if (n == 1) return 0;
        else return (LastRemaining_Solution(n - 1, m) + m) % n;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, M;
        N = in.nextInt();
        M = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = i + 1;
        solution(ListNode.createSingleList(l1)[0], M);
    }
}

CD111 判断一个链表是否为回文结构

/* 整条链表放入栈 */
public class CD111_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static boolean solution(ListNode head)
    {
        Stack<Integer> stack = new Stack<>();
        ListNode pre = head;
        while (pre != null)
        {
            stack.add(pre.val);
            pre = pre.next;
        }
        while (head != null)
        {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N;
        N = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        System.out.println(solution(ListNode.createSingleList(l)[0]));
    }
}

/* 利用快慢双指针, 只把一半链表放入栈 */
public class CD111_2
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static boolean solution(ListNode head)
    {
        ListNode last = head, fast = head;
        Stack<Integer> stack = new Stack<>();
        while (fast != null && fast.next != null)
        {
            last = last.next;
            fast = fast.next.next;
        }
        if (fast != null) last = last.next;
        while (last != null)
        {
            stack.add(last.val);
            last = last.next;
        }
        while (!stack.isEmpty())
        {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N;
        N = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        System.out.println(solution(ListNode.createSingleList(l)[0]));
    }
}

CD112 判断一个链表是否为回文结构(进阶)

/* 将右半区链表反转 */
public class CD112_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static boolean solution(ListNode head)
    {
        ListNode last = head, fast = head, node, temp;
        boolean ans = true;
        Stack<Integer> stack = new Stack<>();
        while (fast != null && fast.next != null)
        {
            last = last.next;
            fast = fast.next.next;
        }
        temp = (fast != null ? reverseList(last.next) : reverseList(last));
        node = temp;
        fast = head;
        while (node != null)
        {
            if (fast.val != node.val)
            {
                ans = false;
                break;
            }
            node = node.next;
            fast = fast.next;
        }
        // 将右半区链表还原
        reverseList(temp);
        return ans;
    }

    public static ListNode reverseList(ListNode head)
    {
        ListNode tail = head.next, temp;
        head.next = null;
        while (tail != null)
        {
            temp = tail.next;
            tail.next = head;
            head = tail;
            tail = temp;
        }
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N;
        N = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        System.out.println(solution(ListNode.createSingleList(l)[0]));
    }
}

CD113 将单向链表按某值划分成左边小、中间相等、右边大的形式

/* 利用数组, 模拟快排(不稳定) */
public class CD113_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head, int pivot)
    {
        ArrayList<ListNode> arr = new ArrayList<>();
        while (head != null)
        {
            arr.add(head);
            head = head.next;
        }
        ListNode[] Nodes = arr.toArray(new ListNode[arr.size()]);
        int idx = 0, small = -1, big = arr.size();
        while (idx != big)
        {
            if (Nodes[idx].val < pivot)
                swapNode(Nodes, idx++, ++small);
            else if (Nodes[idx].val > pivot)
                swapNode(Nodes, idx, --big);
            else idx++;
        }
        for (int i = 1; i < Nodes.length; i++)
            Nodes[i - 1].next = Nodes[i];
        Nodes[Nodes.length - 1].next = null;
        return Nodes[0];
    }

    public static void swapNode(ListNode[] nodes, int i, int j)
    {
        ListNode temp;
        temp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = temp;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, pivot;
        N = in.nextInt();
        pivot = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0], pivot);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

/* 将链表分为大于pivot, 小于pivot, 等于pivot 三段(稳定) */
public class CD113_2
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head, int pivot)
    {
        ListNode small = new ListNode(-1), big = new ListNode(-1), eq = new ListNode(-1), temp;
        ListNode tailSmall = small, tailBig = big, tailEq = eq;
        while (head != null)
        {
            temp = head.next;
            head.next = null;
            if (head.val < pivot)
            {
                tailSmall.next = head;
                tailSmall = head;
            }
            else if (head.val > pivot)
            {
                tailBig.next = head;
                tailBig = head;
            }
            else
            {
                tailEq.next = head;
                tailEq = head;
            }
            head = temp;
        }
        tailEq.next = big.next;
        tailSmall.next = eq.next;
        return small.next;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, pivot;
        N = in.nextInt();
        pivot = in.nextInt();
        int[] l = new int[N];
        for (int i = 0; i < N; i++)
            l[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l)[0], pivot);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

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

/* 剑指offer链表篇 JZ35 复杂链表的复制 */
/* 分成三步 */
public class JZ35_1
{
    public static RandomListNode Clone(RandomListNode pHead)
    {
        RandomListNode head = pHead, res = null, tail = null;
        while (head != null)
        {
            RandomListNode temp = new RandomListNode(-head.label);
            temp.next = head.next;
            head.next = temp;
            head = head.next.next;
        }

        head = pHead;
        while (head != null)
        {
            if (head.random == null)
                head.next.random = null;
            else
                head.next.random = head.random.next;
            head = head.next.next;
        }
        head = pHead;
        while (head != null)
        {
            if (res == null)
            {
                res = tail = head.next;
            }
            else
            {
                tail.next = head.next;
                tail = tail.next;
            }
            head.next = head.next.next;
            head = head.next;
        }
        return res;
    }
}

/* HashMap */
public class JZ35_2
{
    public static RandomListNode Clone(RandomListNode pHead)
    {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = pHead, res = null, tail = null;
        while (p != null)
        {
            RandomListNode temp = new RandomListNode(p.label);
            if (res == null)
                res = tail = temp;
            else
            {
                tail.next = temp;
                tail = tail.next;
            }
            map.put(p, temp);
            p = p.next;
        }
        p = pHead;
        tail = res;
        while (p != null)
        {
            if (p.random == null)
                tail.random = null;
            else
                tail.random = map.get(p.random);
            p = p.next;
            tail = tail.next;
        }
        return res;
    }
}

CD114 两个单链表生成相加链表

/* 栈 */
public class CD114_1
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head1, ListNode head2)
    {
        ListNode head = new ListNode(-1);
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        int add = 0, up = 0;
        while (head1 != null)
        {
            s1.add(head1.val);
            head1 = head1.next;
        }
        while (head2 != null)
        {
            s2.add(head2.val);
            head2 = head2.next;
        }
        while (!s1.isEmpty() || !s2.isEmpty())
        {
            add = up + (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
            up = add / 10;
            add %= 10;
            ListNode temp = new ListNode(add);
            temp.next = head.next;
            head.next = temp;
        }
        if (up != 0)
        {
            ListNode temp = new ListNode(up);
            temp.next = head.next;
            head.next = temp;
        }
        return head.next;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, M;
        N = in.nextInt();
        M = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = in.nextInt();
        int[] l2 = new int[M];
        for (int i = 0; i < M; i++)
            l2[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l1)[0], ListNode.createSingleList(l2)[0]);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

/* 反转链表 */
public class CD114_2
{
    public static class ListNode
    {
        public int val;
        public ListNode next = null;

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

        public static ListNode[] createSingleList(int[] nums)
        {
            ListNode head = new ListNode(-1), tail = head;
            for (int num : nums)
            {
                tail.next = new ListNode(num);
                tail = tail.next;
            }
            return new ListNode[]{head.next, tail};
        }
    }

    public static ListNode solution(ListNode head1, ListNode head2)
    {
        ListNode rev1 = reverseList(head1), rev2 = reverseList(head2), head = new ListNode(-1);
        int up = 0, add = 0;
        while (rev1 != null || rev2 != null)
        {
            add = up + (rev1 == null ? 0 : rev1.val) + (rev2 == null ? 0 : rev2.val);
            up = add / 10;
            add %= 10;
            ListNode temp = new ListNode(add);
            temp.next = head.next;
            head.next = temp;
            rev1 = rev1 == null ? null : rev1.next;
            rev2 = rev2 == null ? null : rev2.next;
        }
        if (up != 0)
        {
            ListNode temp = new ListNode(up);
            temp.next = head.next;
            head.next = temp;
        }
        return head.next;
    }

    public static ListNode reverseList(ListNode head)
    {
        ListNode tail = head.next, temp;
        head.next = null;
        while (tail != null)
        {
            temp = tail.next;
            tail.next = head;
            head = tail;
            tail = temp;
        }
        return head;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, M;
        N = in.nextInt();
        M = in.nextInt();
        int[] l1 = new int[N];
        for (int i = 0; i < N; i++)
            l1[i] = in.nextInt();
        int[] l2 = new int[M];
        for (int i = 0; i < M; i++)
            l2[i] = in.nextInt();
        ListNode res = solution(ListNode.createSingleList(l1)[0], ListNode.createSingleList(l2)[0]);
        while (res != null)
        {
            out.print(res.val + (res.next == null ? "" : " "));
            res = res.next;
        }
        out.flush();
    }
}

标签:head,ListNode,int,左神,next,链表,面试,tail,public
From: https://www.cnblogs.com/VividBinGo/p/17817121.html

相关文章

  • 2008秋-计算机软件基础-单链表练习(1)
    /*--------------------------------------------------------设有一个单链表,头结点为head,为递增有序,写一个完整程序,将其改为递减有序。----------------------------------------------------------*/#include<stdio.h>#include<stdlib.h>//定义结点structnodetype......
  • 2008秋-计算机软件基础-单链表完整示例
    /*---------------------------------------------------------Title:CompletedSimpleLinkedListAuthor:EmanLeeDate:Oct22,2008Fuction:OperationonLinkedStoredLinearList.Thisisacompletedsimplesample.Itisrelatedto......
  • 2008秋季-线性表的链式存储(仅单链表)
    /*---------------------------------------------------------Title:单链表Date:September1,2008Fuction:单链表的初始化,创建,插入,删除,查找结点。参考PPT讲稿或者教材2.2.4节.(p56-63)----------------------------------------------------------*/#inclu......
  • 面试官:你会如何设计QQ中的网络协议?
    引言在设计QQ这道面试题时,我们需要避免进入面试误区。这意味着我们不应该盲目地开展头脑风暴,提出一些不切实际的想法,因为这些想法可能无法经受面试官的深入追问。因此,我们需要站在前人的基础上,思考如何解决这类面试题。我们可以设计一个实际可行的QQ系统,而不是离题太远。设计细......
  • Java面试题(高频、有答案,全网最强)
    这是一套全网最强的Java面试题,吊打网上所有Java面试题。此套面试题的威力:看过这套题的朋友、同事、粉丝参加了面试后说,他们面试被问到的问题大部分(85%以上)都在这套题里,面试通过率高达90%。这是粉丝的真实评价(聊天截图):有人说这套题题目太多了,我说:着急的可以看频率为两颗星及以上的题......
  • 一文搞懂双链表
    前言前面有很详细的讲过线性表(顺序表和链表),当时讲的链表以单链表为主,但在实际应用中双链表有很多应用场景,例如大家熟知的LinkedList。双链表与单链表区别单链表和双链表都是线性表的链式实现,它们的主要区别在于节点结构。单链表的节点包含数据字段data和一个指向下一个节......
  • 【面试题】消息队列面试题总结(RocketMQ版)
    自己整理、总结了一些消息队列相关面试题,并想了一些RocketMQ面试过程中可能会问的知识点。使用消息队列的优点系统解耦比如系统A产生的某个事件,系统B需要感知,简单实现就是在系统A产生事件之后,调用系统B的接口通知系统B,如果此时再增加一个系统C,还需要修改系统A的代码,再加入调用......
  • 常见面试题-TCP三次握手四次挥手
    TCP三次握手/四次挥手参数用途SYN用于启动和建立连接时,同步设备之间的序列号。0到2^32-1的随机数。ACK向另一端确认已经收到SYN,数值为收到SYN增一。SYN-ACK确认之前收到了SYN,数值为自定义值。FIN终止连接。RST重置连接。三次握手三次握手流程为:第一次握手:client请求建立连......
  • 史上最全的Android面试题集锦
    前言由于之前从上海离职,来到深圳找工作。然后准备面试的时候,发现网上很多Android面试题及答案整理都没有答案,在成功的拿到几家公司的offer后(虽然不是阿里、网易这种级别的公司,但对我一个毕业三年的Android开发来说,算是成功的从小公司跳到大公司)自己总结了一些最近面试过的Androi......
  • [左神面试指南] 栈和队列篇
    CD5设计一个有getMin功能的栈/**维护一个最小栈minStack*dataStack每压入一个数,minStack也压入一个当前状态的最小值*/publicclassCD5_1{publicstaticclassSolution{publicStack<Integer>dataStack=newStack<>();publicSt......