[数据结构与算法]LeetCode笔记---Java语言-＞链表

不定时更新—喜欢的可以先收藏一下

141. 环形链表
     思路：采用快慢指针思维，设置一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步，如果有环存在，快慢指针总会相遇，如果没环，快指针会先指向空节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){//判断链表是否为空
            return false;
        }
        ListNode p = head;//这是慢指针
        ListNode q = head.next;//这是快指针
        /* 
        因为要判断快慢指针是否相遇
        我们判断的条件是快慢指针指向的节点是否相同  
        所以在这里我们先让快指针指向慢指针的下一个节点，避免刚开始两个节点指向同一个位置。
        */
        while(p!=q&&q!=null&&q.next!=null){
            /*只要两个指针没有指向同一个节点，并且快指针没有指向空节点，就往下走，因为
            快指针一次走两个，所以我们还要判断快指针的下一个节点是不是空节点*/
            p = p.next;
            q = q.next.next;
        }
        //当走出循环后，要么pq相遇，要么p指向了空节点
        return q!=null&&q.next!=null;//如果p或者p的next不等于null，那么就说明链表内有环
    }
}

142. 环形链表 II
     思路： 寻找环的起始点：因为快指针一直在追慢指针，当慢指针走到环起点的时候，快指针已经哦足了慢指针的2倍，当快慢指针在环中相遇的时候，相遇位置到环起点的距离和链表头节点到环起点的距离相同，让一个节点返回头节点，两个节点一起走，相遇位置就是环起点

这里要注意，在我们写的代码中，快节点出发时比慢节点早一个节点，所以实际再环中相遇的位置比设想的早了一次，所以环中的那个节点要再往前走一次，才能保证两个会相遇。

-------画图可以方便理解

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){//先判断列表是否为空
            return null;
        }
        ListNode q = head.next;
        ListNode p = head;
        while(p!=q&&q!=null&&q.next!=null){
            p = p.next;
            q = q.next.next;
        }
        //该题我们依然要查看是否有环
        if(q!=null&&q.next!=null){//if=true代表有环
            /* 这里要注意，在我们写的代码中，快节点出发时比慢节点早一个节点，所以实际再环中相遇的位置比设想的早了一次，所以环中的那个节点要再往前走一次，才能保证两个会相遇。 */
            p=p.next;//p向前走一个
            q = head;//q直接返回链表头
            while(p!=q){//只要p和q没有相遇，那么就一直走
                p = p.next;
                q = q.next;
            }
            return p;//当终止了while循环就代表p和q都达到了环起点
        }else{//代表无环---返回null
            return null;
        }
    }
}

202.快乐数
思路 ：虽然不是链表，但是用到了上面的快慢指针思想。因为如果到不了1，就意味着再某一段数字内陷入了循环状态，陷入了循环状态就代表有环。

class Solution {
    public boolean isHappy(int n) {
        int p = n;//慢指针
        int q = n;//快指针
        do{//我们这里用了dowhile循环，让他俩先走一次，避免刚出发就终止循环
            p = getNum(p);
            q = getNum(getNum(q));
        }while(q!=p&&q!=1);//只要他俩不相等并且走的快的q不等于1就继续循环
        return q==1;//如果q最后=1就说明是快乐数，不等于1说明遇到了环，不是快乐数
    }
    public int getNum(int i){//求平方和的方法
        int z = 0;
        while(i!=0){
            z = z + (i%10)*(i%10);
            i = i / 10;
        }
        return z;
    }
}

206.反转链表
思路：
（1）设立三个链表节点（迭代的方法）：
cur的next = pre，pre再等于cur，cur=next，next = cur.next
pre->反转以后链表的头节点
cur->未反转链表的头节点
next->未反转链表的头节点的下一位

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null||head.next ==null)//有一个节点或没有节点就不用反转了
            return head;
        ListNode pre = null;//反转以后链表的头节点
        ListNode cur = head;//未反转链表的头节点
        ListNode next = cur.next;//未反转链表的头节点的下一位
        while(cur!=null){//只要cur！=null就说明没有反转完成
            cur.next = pre;//让cur的next指向反转以后的头结点，因为后面的节点反转之后就成为了前面的节点前一个节点，这时cur就成为了反转之后链表的头结点
            pre = cur;//pre=cur。pre再次变成反转之后的头结点
            cur = next;//cur指向next节点和反转之后的链表断开
            if(next!=null)//如果还有下一个节点，那么next就再往下走一个
                next = next.next;
        }
        return pre;
    }
}

（2）使用递归的方法 ：将该节点插入到该节点后面的所有节点的反转的末尾
leetcode：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
         if(head == null||head.next ==null)
            return head;
        /*
        head是当前要反转的链表的第一个节点
        我们记录一下head的下一个节点,让tail=head，tail就是head节点后面的所有节点的反转的末尾
        */    
        ListNode tail = head.next;
        ListNode re = reverseList(head.next);//递归调用自己，翻转head后面的链表
        head.next = tail.next;//在这里tail代表了尾部节点，tail.next在这里等于null
        tail.next = head;//将head放到tail的后面，完成插入
        return re; //返回反转之后的链表
    }
}

92. 反转链表 II
    思路：先找到m的前一个位置，然后反转该位之后的前n个链表。
    用到了虚拟头节点（建立一个节点，指向链表的头节点）