链表（简单）

环形链表

  • @快慢指针(相遇则为环形链表)

 public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null)   return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow){
           if(fast == null || fast.next == null)   return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

  • @哈希表

public boolean hasCycle1(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<>();
        while (head != null) {
            if (nodesSeen.contains(head)) {
                return true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;
    }

环形链表II


     7<-6<- 5
      |     ^
      |     |
0->1->2->3->4
[-----]


我们设置快慢两个指针，fast, slow fast一次前进两步，
slow一次前进一步，
设a为第一个节点到入环节点的距离。 a=[0->2]
设b为入环口到相遇点的距离。b=[2->6]
设c为相遇点到入环口的距离。c=[6->2]
当fast，和slow相遇的时候，fast经过的节点是slow的两倍，设slow经过的节点数为S
根据上面的设置 可知 S=a+b ,2S=a+b+c+b，可知 a=c,此时让slow回到第一个节点，
fast处于第一次相遇的节点，此时slow从第一个节点出发，因为a=c，所以fast，
和slow会在入环口第二次相遇，得到要求的节点。
----------------------------------------------------------------
public ListNode detectCycle(ListNode head)
    {
        if(head==null)
        return head;
        // 步骤一：使用快慢指针判断链表是否有环,必须快慢指针为同一起跑线
        ListNode fast = head, slow = head;
        boolean hasCycle = false;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast =fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 步骤二：若有环，找到入环开始的节点
        if (hasCycle)
        {
            ListNode q = head;
            while (slow!= q)
            {
                slow = slow.next;
                q = q.next;
            }
            return q;
        } else
            return null;
    }

返回链表倒数第n个节点

 public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode quick=head;
        ListNode slow=head;
        while(k>0){
            quick=quick.next;
            k--;
        }
        while(quick!=null)
        {
            quick=quick.next;
            slow=slow.next;
        }
        return slow;
       
    }

public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k<=0)
        {
            return null;
        }
        ListNode n1=head,n2=head;
        int count=0;
        int index=k;
        while(n1!=null)
        {
           n1=n1.next;
            count++;
            if(k<1)
            {
                n2=n2.next;
            }
            k--;
            
        }
        if(count<index)
        {
            return null;
        }
        return n2;

删除链表倒数第n个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp=new ListNode(0);
        temp.next=head;
        ListNode quick=temp;
        ListNode slow=temp;
        while(n>0)
        {
            quick=quick.next;
            n--;
        }
        while (quick.next!=null)
        {
            quick=quick.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return temp.next;
    }

合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
        {
            return l2;
        }
        if(l2==null)
        {
            return l1;
        }
        ListNode dhead=new ListNode(0);
        dhead.next=l1.val<=l2.val?l1:l2;
        if(dhead.next==l1)
        {
            l1=l1.next;
        }
        else {
            l2=l2.next;
        }
        ListNode temp=dhead.next;
        while (l1!=null&&l2!=null)
        {
            if(l1.val<=l2.val)
            {
                temp.next=l1;
                temp=temp.next;
                l1=l1.next;
            }
            else {
                temp.next = l2;
                temp=temp.next;
                l2 = l2.next;
            }
        }
        temp.next=l1==null?l2:l1;
        return dhead.next;
    }

反转链表

@迭代

public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

@递归

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

回文链表

@双指针

public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)
        {
            return true;
        }
        ListNode slow=head,quick=head,pre=null;
        //1.快慢指针,找到链表的中点。
        while(quick!=null&&quick.next!=null)
        {
            slow=slow.next;
            quick=quick.next.next;
        }
        //2.将slow之后链表反转
        while(slow!=null)
        {
            ListNode next=slow.next;
            slow.next=pre;
            pre=slow;
            slow=next;

        }
        //3.前后链表进行比较，注意若为奇数链表，多1一个节点，然而并不影响判断回文
        while (head!=null&&pre!=null)
        {
            if(head.val!=pre.val)
                return false;
            head=head.next;
            pre=pre.next;
        }
        return true;
    }

 public boolean isPalindrome1(ListNode head) {
        // 要实现 O(n) 的时间复杂度和 O(1) 的空间复杂度，需要翻转后半部分
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 根据快慢指针，找到链表的中点
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow.next);
        while(slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head){
        // 递归到最后一个节点，返回新的新的头结点
        if (head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

  • @数组缓存

//单链表检查回文串的难点就在于，只能沿一个方便遍历，双指针无法进行
//于是我们就想到可以借用一个辅助数组，将链表节点拷贝到数组中，
// 然后再数组中双指针检查，空间复杂度为O(n),时间复杂度O(n)
    public boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        // 1、拷贝到数组
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        int lo = 0;               // 头指针
        int hi = list.size() - 1; // 尾指针
        // 2、双指针检查
        while (lo <= hi) {
            if (!list.get(lo).equals(list.get(hi))) {
                return false;
            }
            lo++;
            hi--;
        }
        return true;
    }

  • @栈

public boolean isPalindrome3(ListNode head) {
    Stack<ListNode> s=new Stack();
    ListNode p=head;
    while(p!=null)
    {
        s.push(p);
        p=p.next;
    }
    p=head;
    while(!s.isEmpty())
    {
        if(s.peek().val!=p.val)
        {
            return false;
        }
        s.pop();
        p=p.next;
    }
    return true;
}
image.png

  • @递归

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode h1 = headA, h2 = headB;
        while (h1 != h2) {
            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }
        return h1;
    }

  • @非递归

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1=0;
        int len2=0;
        ListNode n1=headA;
        ListNode n2=headB;
        while(n1!=null)
        {
            n1=n1.next;
            len1++;
        }
        while(n2!=null)
        {
            n2=n2.next;
            len2++;
        }

        int cha=len2-len1;
        if(cha>0)
        {
            while(cha>0)
            {
                cha--;
                headB=headB.next;
            }

        }
        if(cha<0)
        {
            while(cha<0)
            {
                cha++;
                headA=headA.next;
            }
        }
        while(headA!=null&&headB!=null)
        {
            if(headA==headB)
            {
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }

删除排序链表中的重复元素

 public ListNode deleteDuplicates(ListNode head) {
        ListNode n=head;
        while(n!=null&&n.next!=null){
            if(n.val==n.next.val)
            {
                ListNode cur=n;
                while(n.val==n.next.val)
                {
                        n=n.next;
                        if(n.next==null)
                        {
                            break;
                        }
                }
                cur.next=n.next;
            }
            n=n.next;
        }

        return head;
    }

两两交换链表中的节点

  • @递归

 public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode next = head.next;
            head.next = swapPairs(next.next);
            next.next = head;
            return next;
        }

  • @递归二

public ListNode swapPairs(ListNode head) {
        ListNode temphead=new ListNode(0);
        temphead.next=digui(head);
        return temphead.next;
    }
    public ListNode digui(ListNode temp)
    {
        if(temp==null)
            return null ;
        ListNode one=temp;
        ListNode two=temp.next;
        if(two!=null){
            one.next=digui(two.next);
        }
        else{
            one.next=null;
        }
        if(two!=null)
        {
            two.next=one;
            return two;
        }
        else{
            return one;
        }
    }

  • 非递归

public ListNode swapPairs(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode n1=head;
        ListNode n2=head.next;
        if(n2==null) {
            return n1;
        }
        ListNode x=new ListNode(0);
        x.next=n2;
        while(n1!=null&&n2!=null)
        {
            n1.next=n2.next;
            ListNode temp=n1;
            n2.next=n1;
            n1=n1.next;
            if(n1!=null) {
                n2=n1.next;
            } else {
                n2=null;
            }if(n2==null) {
                temp.next=n1;
            } else {
                temp.next=n2;
            }
        }
        return x.next;
    }
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,539评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,911评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,337评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,723评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,795评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,762评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,742评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,508评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,954评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,104评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,736评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2赞 352