链表反转

非递归

private ListNode revarse(ListNode head)
    {
        //退出条件
        ListNode newHead=null;
        while (head!=null)
        {
            ListNode temp=newHead;
            newHead=head;
            head=head.next;
            newHead.next=temp;
        }
        return newHead;
    }

递归

A->B->C->D->null
1->2->3->4->null
1.head 为 D 直接返回D
2.head 为 C head->next是D D->next是C C->next是D->next 也就是null
A->B->D-C->null
3.head 为 B head->next是D D->next是B B->next是D->next 也就是C
A->D->B->C

private ListNode revarse(ListNode head)
    {
        //退出条件
        if(head==null|head.next==null)
        {
            return head;
        }
        ListNode newHead=revarse(head.next);
        ListNode temp=head.next;
        head.next=temp.next;
        temp.next=head;
        return newHead;
    }

判断链表是否是回文

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
采用快慢指针
while (fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        //用快慢双指针
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode reHead=revarse(slow);
        while (reHead!=null)
        {
            if(head.val!=reHead.val)
            {
                return false;
            }
            reHead=reHead.next;
            head=head.next;
        }
        return true;
    }
    private ListNode revarse(ListNode head)
    {
        //退出条件
        ListNode newHead=null;
        while (head!=null)
        {
            ListNode temp=newHead;
            newHead=head;
            head=head.next;
            newHead.next=temp;
        }
        return newHead;
    }
}

递归实现合并两个有序链表

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
每次返回数较小节点。

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1==null)//退出条件
        {
            return l2;
        }
        if(l2==null)
        {
            return l1;
        }
        if(l1.val>l2.val)
        {
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
    }

环形链表

删除自身节点

此种方法就是将遍历过的节点都指向自己 当有节点指向已经遍历过的节点（或者他指向自身我们就返回错误）

public boolean hasCycle(ListNode head) {
        //逐个删除
        //退出条件
        if(head==null||head.next==null)
        {
            return false;
        }
        if(head==head.next)//如果该节点指向了自己
        {
            return true;
        }
        ListNode nextNode=head.next;
        //删除当前节点
        head.next=head;//标记我们已经访问了该节点
        return hasCycle(nextNode);//开始查看下一个节点
    }
    非递归
    public boolean hasCycle(ListNode head) {
        while (head!=null&&head.next!=null)
        {
            if(head==head.next)
            {
                return true;
            }
            ListNode temp=head;
            head=head.next;
            temp.next=temp;
        }
        return false;
    }

使用快慢指针

public boolean hasCycle(ListNode head) {
    if (head == null)
        return false;
    //快慢两个指针
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        //慢指针每次走一步
        slow = slow.next;
        //快指针每次走两步
        fast = fast.next.next;
        //如果相遇，说明有环，直接返回true
        if (slow == fast)
            return true;
    }
    //否则就是没环
    return false;
}