【数据结构与算法 | 基础篇】[链表专题]力扣21, 234

简介: 【数据结构与算法 | 基础篇】[链表专题]力扣21, 234

1. 力扣21 : 合并两个有序链表

题 :

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 
 
 
示例 1:
 
 
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
 
输入:l1 = [], l2 = []
输出:[]
示例 3:
 
输入:l1 = [], l2 = [0]
输出:[0]
 
 
提示:
 
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路 :双指针

先判断list1,list2是否为空的三种情况,再按照双指针法依次将两个链表串起来.head记录头指针的位置.p指针起到串联的作用.

解 :

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode p;
        if (list1.val > list2.val) {
            p = list2;
            list2 = list2.next;
        } else {
            p = list1;
            list1 = list1.next;
        }
        ListNode head = p;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                p.next = list2;
                p = p.next;
                list2 = list2.next;
            } else {
                p.next = list1;
                p = p.next;
                list1 = list1.next;
            }
        }
        if (list1 == null) {
            p.next = list2;
        } else {
            p.next = list1;
        }
        return head;
    }
}

2. 力扣234 : 回文链表

题 :

给你一个单链表的头节点 head ,请你判断该链表是否为
回文链表
。如果是,返回 true ;否则,返回 false 。
 
 
 
示例 1:
 
 
输入:head = [1,2,2,1]
输出:true
示例 2:
 
 
输入:head = [1,2]
输出:false
 
 
提示:
 
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
 
 
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

思路 : 辅助数组 + 双指针

借助辅助数组,从而判断数组是否是回文数组.该解法空间复杂度较高O(n).但时间复杂度为O(n).

解 :

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode p = head;
        int count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }
        int[] a = new int[count];
        p = head;
        count = 0;
        while (p != null) {
            a[count++] = p.val;
            p = p.next;
        }
        boolean flag = true;
        int last = count - 1;
        int hed = 0;
        for (int i = count / 2; i > 0; i--) {
            if (a[hed++] != a[last--]) {
                flag = false;
            }
        }
        return flag;
    }
}
相关文章
|
20小时前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
8 2
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
3天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
3天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
3天前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
3天前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
3天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
8 0