反转链表、环形链表和删除某一个节点

2020-07-08  本文已影响0人  YYFast

反转链表、环形链表和删除某一个节点

查看关于网上的一些反转链表的思路,发现步骤十分复杂,在学习了小码哥的数据结构以后,整理了一下,作为学习笔记;

链表:有一个head指针,指向链表的第一个节点;
节点ListNode: val 即节点存储的元素;next指针指向下一个节点或者null;

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

1 链表反转

LeetCode链接

1.1 思路一: 递归实现

前提条件: 我们现在能拿到的就是head也就是第一个节点

1、方法reverseList要传入head实现如下效果:

实现效果

返回一个newHead指向原链表的最后一个节点;

2、递归思路关键点:当reverseList方法传入的节点是head.next的时候:

传入head.next效果

最后4节点的next指向null;

代码如下:

//递归实现
public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) return head; //步骤1
    ListNode newHead = reverseList(head.next);         //步骤2
    head.next.next = head;                             //步骤3
    head.next = null;                                  //步骤4
    return newHead;
}

1.2 思路二: 非递归实现

前提条件: 我们现在能拿到的就是head也就是第一个节点,所以要从第一个节点开始遍历反转,串起来;

图1 反转前

通过head和newHead,及tmp将节点一个一个串起来:

图2 第一个节点被串起来

代码:

    //非递归
    public ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;  //注意
            head.next = newHead;       //步骤1
            newHead = head;            //步骤2
            head = tmp;                //步骤3
        }
        return newHead;
    }

2 环形链表

LeetCode链接

image.png

判断一个链表是否有环,需要用到一个思想:快慢指针
slow指针:每次循环挪动一个节点;
fast指针:每次挪动两个节点;

当slow == fast时表示有环,返回true
当fast == null 或者 fast.next == null的时候没有环,返回false

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next; //为了后面的判断第一次slow == fast不成立
        while(fast != null && fast.next != null){
           if(slow == fast) return true;
           slow = slow.next;
           fast = fast.next.next;
        }
        return fasle;
    }

3 删除链表的某一个节点

LeetCode链接

image.png

删除链表中的某一个节点,只要弄清楚思路就很简单:

    public void deleteNode(ListNode node) {
       node.val = node.next.val;   //步骤1
       node.next = node.next.next; //步骤2    
    }

上一篇下一篇

猜你喜欢

热点阅读