LeetCode | 链表(1)

LeetCode | 链表(1)

160. 相交链表

题目

很久之前做的题了,其是把这道题放在 LeetCode 系列第一的位置是有原因的,当时做这道题,真的想了很久,然后上手写题,虽然也通过了,但是代码特别繁冗,后来看到了大神的题解,我彻底跪了,太震撼了,我知道我很菜,但我不知道我竟然那么菜,没有对比就没有伤害。然后就下定决心,学习别人优秀的解法和代码风格,努力提升自己。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode pa = headA, pb = headB;
        while(pa!=pb) {
            pa = pa==null ? headB : pa.next;
            pb = pb==null ? headA : pb.next;
        }
        return pa;
    }
}

206. 反转链表

题目

最开始想到的最直接的方法,使用一个栈,按顺序把链表节点压入栈中,再弹出重建链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.Stack;

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        Stack<ListNode> stack = new Stack<>();
        while(head!=null) {
            stack.push(head);
            head = head.next;
        }
        ListNode ans = stack.pop();
        ListNode p = ans;
        while(!stack.isEmpty()) {
            p.next = stack.pop();
            p = p.next;
        }
        // 注意边界,next赋值null,否则会变成循环链表
        p.next = null;
        return ans;
    }
}

不过,因为有入栈和出栈的操作,相当于遍历了两次链表,很费时间,而且空间复杂度为 $ O(N) $,其实有更快的方法,可以一次遍历实现

递归版:递归本质就是利用了方法执行的栈结构,无需使用额外的空间,要注意停止递归的返回条件,如果链表特别长,可能爆栈

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode oldNext = head.next;
        ListNode newHead = reverseList(head.next);
        oldNext.next = head;
        // 注意边界,head已经变成尾节点,next赋值null
        head.next = null;
        return newHead;
    }
}

迭代版:使用两个指针,一个指向新链表的(实际的)头节点,另一个去遍历链表,遍历过程中不断将该节点的next指向头节点,旧链表的head就在遍历过程中成为一个标识遍历进度的指针

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode newHead = head, p = head.next;
        while(p!=null) {
            head.next = p.next;
            p.next = newHead;
            newHead = p;
            p = head.next;
        }
        return newHead;
    }
}

21. 合并两个有序链表

题目

注意题目要求“新链表是通过拼接给定的两个链表的所有节点组成的”,所以不能新建一个链表,再把 l1 和 l2 的 val 赋给新链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode ans,p,p1,p2;
        if(l1.val>l2.val) {
            ans = l2;
            p1 = l1;
            p2 = l2.next;
        }else {
            ans = l1;
            p1 = l1.next;
            p2 = l2;
        }
        p = ans;
        while(p1!=null&&p2!=null) {
            if(p1.val>p2.val) {
                p.next = p2;
                p2 = p2.next;
            }else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        p.next = p1==null ? p2 : p1;
        return ans;
    }
}