欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode刷题之链表(持续更新)

程序员文章站 2024-03-16 16:09:40
...

链表数据结构:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

1. 反转链表

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

public class Test1 {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode prev = null;
        while(head != null) {
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }

2. 两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

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

public class Test2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {  //先进行形参的判断,提高执行效率
             return null;
        }
        if (l1 == null) {  //因为上面判断了l1和l2,所以这里如果l1是null,那么l2必然有值,直接返回l2即可
            return l2;
        }
        if (l2 == null) {  //理由同上
             return l1;
        }
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (true) {
            if (l1 != null) {
                temp.val = temp.val + l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                temp.val = temp.val + l2.val;
                l2 = l2.next;
            }
            temp.next = new ListNode(temp.val / 10);
            temp.val = temp.val % 10;
            if (l1 == null && l2 == null) {
                temp.next = (temp.next.val == 0 ? null : temp.next);
                break;
            }
            temp = temp.next;
        }
        return result;
    }
}

3. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

public class Test3 {

    //方法1
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = null;
        result = merge(result, l1, l2);
        return result;
    }

    public ListNode merge(ListNode result, ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) {
            return null;
        }
        if(l1 == null && l2 != null) {
            return l2;
        }
        if(l1 != null && l2 == null) {
            return l1;
        }
        if(l1.val > l2.val) {
            result = l2;
            l2 = l2.next;
        } else {
            result = l1;
            l1 = l1.next;
        }
        result.next = merge(result.next, l1, l2);
        return result;
    }

    //方法2
    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }
        ListNode head = l1.val < l2.val ? l1 : l2;  //满足条件的链结点
        ListNode other = l1.val >= l2.val ? l1 : l2;  //不满足条件的链结点
        ListNode preHead = head;  //当前位置(满足条件)
        ListNode preOther = other;  //当前位置(不满足条件)
        while (preHead != null) {
            ListNode next = preHead.next;
            if(next != null && next.val > preOther.val) {
                preHead.next = preOther;
                preOther = next;
            }
            if(preHead.next == null) {
                preHead.next = preOther;
                break;
            }
            preHead = preHead.next;
        }
        return head;
    }
}

 

相关标签: LeetCode