力扣练习(一)

力扣 2020-03-10 132 次浏览 本文字数:3246字

本文主要内容:力扣206.反转链表、力扣141.环形链表、力扣203.删除链表元素

反转链表

反转链表题目

解法一:递归思想
递归思想原理图

思想简述:假设我们通过ListNode newHead = reverseList(head.next)已经完成了1-4数字的反转,那么现在的问题就是如何将4指向5,这样问题就解决了。我们首先让4的指针指向5:head.next.next = head(因为已经完成反转,现在4的指针指向null),然后让head = null即可,同时处理边界问题,如果head为空或head.next = null,返回head本身即可

代码展示:

class Solution {
public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

解法二:迭代思想
迭代思想原理图

思想简述:我们首先通过设置一个节点newHead,让其指向null,然后我们让head.next = newHead;然后将newHead = head; 但此时我们会发现head.next与head之间的指针给断了,所以我们需要设置另一个变量,将其指向head.next即:ListNode tmp = head.next;然后将head指向tmp即:head = tmp;同时处理边界问题,只要head不为空即可

代码展示:

class Solution {
public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
        while(head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

环形链表

环形链表问题

思想简述:我们只需一快一慢两个节点,如果快节点等于慢节点,即可证明链表中存在环,同时需要考虑边界问题(见代码部分)

代码展示:

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null){
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;               //注意fast需要比slow快2步才能追上
        }
       return false;
    }
}

移除链表元素

删除链表元素问题

思想简述:在我们自定义删除链表元素时,我们可以获取到删除节点的前一个节点,这样使用前一个节点直接指向删除元素节点的下一个节点即可完成任务,现在我们既然无法获得前一个节点,那么我们就可以设置虚拟节点来模拟前一个节点(哨兵节点)

代码展示:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;

        ListNode sentinel = new ListNode(0);
        sentinel.next = head;

        ListNode prev = sentinel;
        while(prev.next != null){
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            }else {
                prev = prev.next;
            }
        }
        return sentinel.next; 
    }
}

本文由 WarlockMarten 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。