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

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

链表：有一个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、递归循环结束临界条件；

  • 当head == null时，应直接返回null，即head；
  • 当head.next ==null时，应直接返回head；

• 步骤2、递归实现，传入head.next，实现效果如上图；

• 步骤3、将节点4，即head.next,指向head

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;
    }

• 创建一个newHead指向null，这个newHead将会是反转后链表的头部；
• 步骤1、将head.next指向newHead（即第一个节点的next指向newHead）；
• 步骤2、将newHead指向head（如图2所示第一个节点5就被newHead串起来了）；
• 步骤3、将head指针指向下一个节点4 （循环操作）
• 注意 ： 在第1步将head.next指向newHead时：因为没有指针指向后面的链表，所以后面的链表可能会被销毁，所以要先创建一个tmp指针指向head.next;

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

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

• 步骤1、用让当前节点node的下一个节点的值val覆盖当前节点的值
• 步骤2、当前节点的指针指向next.next

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