• Leetcode链表相关题目

    目录

    leetcode2. 两数相加

    题目描述
    我的解法：

    public class Leetcode2 {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

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

    public static void main(String[] args) {
        //2->4->3 5->6->4 = 7-> 0 -> 8
        //342+465=807


//        int[] a = new int[]{2, 4, 3};
//        int[] b = new int[]{5, 6, 4};

        int[] a = new int[]{2, 4};
        int[] b = new int[]{5, 6, 4};


        ListNode headA = initList(a);
        ListNode headB = initList(b);

        printList(headA);
        printList(headB);

        ListNode headC = addTwoNumbers(headA, headB);

        printList(headC);


    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cA = l1;
        ListNode cB = l2;

        ListNode headC = new ListNode(-1);
        ListNode initC = headC;

        int add = 0;

        while (cA != null || cB != null || add != 0) { //add!=0 是处理链表增长问题
            ListNode temp = new ListNode();

            int x = cA == null ? 0 : cA.val;
            int y = cB == null ? 0 : cB.val;

            int result = x + y + add;
            if (result >= 10) {
                temp.val = result % 10;
                add = 1;
            } else {
                temp.val = result;
                add = 0;
            }
            initC.next = temp;
            initC = initC.next;

            if (cA != null) {
                cA = cA.next;
            }

            if (cB != null) {
                cB = cB.next;
            }
        }


        return headC.next;
    }


    public static void printList(ListNode printC) {
        while (printC != null) {
            System.out.print(printC.val + " ");
            printC = printC.next;
        }
        System.out.println();
    }

    public static ListNode initList(int[] a) {
        ListNode lista = new ListNode(-1);
        ListNode init = lista;
        for (int i = 0; i < a.length; i++) {
            ListNode temp = new ListNode(a[i]);
            init.next = temp;
            init = init.next;
        }
        return lista.next;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    leetcode21.合并两个有序链表

    题目描述
    方法一：把第一个值最小的链表，当作被插入的链表，再把另外一个链表插入到这个链表。

    public class Leetcode21 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

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

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

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }

        if (list2 == null) {
            return list1;
        }

        ListNode baseNode, moveNode;
        if (list1.val < list2.val) {
            baseNode = list1;
            moveNode = list2;
        } else {
            baseNode = list2;
            moveNode = list1;
        }

        //把moveNode插入baseNode
        ListNode p = moveNode;
        ListNode b = baseNode; 

        while (p != null) {
            if (b.next == null) {
                b.next = p;
                b = b.next;
                p = p.next;
                break;
            } else if (p.val <= b.next.val) {
                ListNode temp = p.next;

                p.next = b.next;
                b.next = p;

                b = b.next;
                p = temp;

            } else {
                b = b.next;
            }


        }
        return baseNode;
    }

    public static void main(String[] args) {
//        int[] l1 = new int[]{1, 2, 4};
//        int[] l2 = new int[]{1, 3, 4};

        int[] l1 = new int[]{-9, 3};
        int[] l2 = new int[]{5, 7};
        ListNode head1 = getHead(l1);
        ListNode head2 = getHead(l2);

        ListNode printNode = new Leetcode21().mergeTwoLists(head1, head2);
        while (printNode != null) {
            System.out.print(printNode.val + " ");
            printNode = printNode.next;
        }
    }

    private static ListNode getHead(int[] l1) {
        if (l1.length <= 0) {
            return null;
        }
        ListNode head = new ListNode(l1[0]);
        ListNode h = head;
        for (int i = 1; i < l1.length; i++) {
            ListNode temp = new ListNode(l1[i]);
            h.next = temp;
            h = h.next;
        }
        return head;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95

    方法二：新建一个链表，从两个链表中取值，谁小用谁的。

    
public class Leetcode21_2 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

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

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

    public static void main(String[] args) {
                int[] l1 = new int[]{1, 2, 4};
        int[] l2 = new int[]{1, 3, 4};

//        int[] l1 = new int[]{-9, 3};
//        int[] l2 = new int[]{5, 7};
        ListNode head1 = getHead(l1);
        ListNode head2 = getHead(l2);

        ListNode printNode = new Leetcode21_2().mergeTwoLists(head1, head2);
        while (printNode != null) {
            System.out.print(printNode.val + " ");
            printNode = printNode.next;
        }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(-1);//最终返回head.next

        ListNode p = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return head.next;
    }

    public static ListNode getHead(int[] l1) {
        if (l1==null) {
            return null;
        }
        ListNode head = new ListNode(-1);
        ListNode h = head;
        for (int i = 0; i < l1.length; i++) {
            ListNode temp = new ListNode(l1[i]);
            h.next = temp;
            h = h.next;
        }
        return head.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    leetcode206. 反转单链表

    题目描述

    1. 原地反转
    public class Test {
    static class Node {
        int value;
        Node next;
    }

    public static void main(String[] args) {
        int[] g = new int[]{1, 2, 3, 4};
        Node head = new Node();
        head.value = -1;

        Node init = head;
        for (int i = 0; i < g.length; i++) {
            Node temp = new Node();
            temp.value = g[i];
            init.next = temp;
            init = init.next;
        }

        //原地反转

        Node newRoot = head.next;
        Node tail = head.next;
        Node cur = newRoot.next;
        while (cur != null) {
            tail.next = cur.next; //尾巴指向当前节点
            cur.next = newRoot; //当前节点指向新根节点

            newRoot = cur; //新根节点移动到当前节点，准备下一次循环
            cur = tail.next;//当前节点指向尾巴的下一个节点，为下一次循环做准备
        }


        printList(newRoot);

    }

    public static void printList(Node print) {
        while (print != null) {
            System.out.print(print.value + " ");
            print = print.next;
        }
        System.out.println();
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    1. 新建链表，用头插法插入。
        public static ListNode reverseByCreateAnother(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        ListNode point = head;

        while (point != null) {
            newHead = addHead(point, newHead);
            point = point.next;
        }
        return newHead;
    }

    public static ListNode addHead(ListNode newNode, ListNode targetHead) {
        ListNode temp = new ListNode(newNode.val, null);
        temp.next = targetHead;
        return temp;
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
  • 相关阅读:
    束带机安全使用须知
    C++头文件、源代码文件简单总结
    知识图谱(4)图算法
    CentOS 7：服务器环境搭建
    qt的xml读写和QDomDocument、QDomElement、QDomNode、QDomNamedNodeMap讲解
    Java系列技术之JavaScript基础（从入门开始）③
    如何管理oralce口令文件和参数文件
    数据中台不是万能钥匙，企业需求才是数据中台建设的根本
    Mapbox 与 Babylon.js 可视化 构建房子
    文件系统考古2：1984 - BSD Fast Filing System
  • 原文地址：https://blog.csdn.net/zhangjin1120/article/details/136369422