链表相关

leetcode 2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  输出：7 -> 0 -> 8  原因：342 + 465 = 807

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int jishu = 0;
        ListNode res = new ListNode(-1);
        ListNode tmp = res;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + jishu;
            res.next = new ListNode((sum) % 10);
            res = res.next;
            jishu = (sum) / 10;
            l1 = l1.next;
            l2 = l2.next;

        }
        while (l1 != null) {
            int sum = l1.val + jishu;
            res.next = new ListNode((sum) % 10);
            res = res.next;
            jishu = (sum) / 10;
            l1 = l1.next;

        }
        while (l2 != null) {
            int sum = l2.val + jishu;
            res.next = new ListNode((sum) % 10);
            res = res.next;
            jishu = (sum) / 10;
            l2 = l2.next;

        }
        if (jishu == 1) {
            res.next = new ListNode(1);
        }
        return tmp.next;
    }

21. 合并两个有序链表

public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode tmp = new ListNode(0);
        ListNode res = tmp;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tmp.next = l1;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                l2 = l2.next;

            }
            tmp = tmp.next;
        }

        while (l1 != null) {
            tmp.next = l1;
            l1 = l1.next;
            tmp = tmp.next;
        }

        while (l2 != null) {
            tmp.next = l2;
            l2 = l2.next;
            tmp = tmp.next;
        }
        return res.next;
    }

    //递归写法
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if(l1.val<l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

leetcode 82. 删除排序链表中的重复元素 II

//递归写法
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        if (head.next != null && head.val == head.next.val) {
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            //去掉所有重复的数字，然后进行递归
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
        }
        return head;
    }
    //非递归写法
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = new ListNode(-1);
        ListNode node = res;
        while (head != null) {
            boolean dup = false;
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
                dup = true;
            }
            if (!dup) {
                res.next = head;
                res = res.next;

            }
            head = head.next;
        }
        res.next = null;  //防止res后面还有重复的节点
        return node.next;
    }

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:  输入: 1->1->2   输出: 1->2

示例 2:   输入: 1->1->2->3->3   输出: 1->2->3

public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = head;
        while (head != null && head.next != null) {
            //相等的话就删除下一个节点
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                //不相等的话向前移动一位
                head = head.next;
            }
        }
        return res;
    }


    //递归写法
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            //如果值和下一个值相同，删掉这个节点，即直接返回下一个节点
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
        }
        return head;

    }

leetcode 86. 分隔链表

public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode more = new ListNode(-1);
        ListNode moreHead = more;
        ListNode less = new ListNode(-1);
        ListNode lessHead = less;

        while (head != null){
            if(head.val < x){
                less.next = head;
                less = less.next;
            }else {
                more.next = head;
                more = more.next;
            }
            head = head.next;
        }
        more.next = null;  //这步不要忘记，不然链表就出现环了
        less.next = moreHead.next;
        return lessHead.next;
        
    }