環(huán)形鏈表

• @快慢指針(相遇則為環(huán)形鏈表)

鏈表題解法中茬射，有一種解法是非常重要的管引，就是快慢指針（雙指針）
基本原理：定義兩個指針闸迷，一個快嵌纲，一個慢，慢指針指向頭結(jié)點腥沽，快指針指向頭結(jié)點的下一個節(jié)點逮走，快指針每次走兩步，慢指針每次走一步今阳，如果鏈表為環(huán)形师溅，則兩指針遲早會相遇，如果快指針為空了盾舌，則說明不存在環(huán)形鏈表

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

• @哈希表

可以用哈希表墓臭，如果為環(huán)形鏈表則迭代過程中結(jié)點元素遲早會重復（并不推薦，相比雙指針法速度太慢妖谴，哈希表插入以及計算重復都會消耗大量性能）

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

環(huán)形鏈表II

image.png

關鍵在于找規(guī)律窿锉，借鑒評論熱解，設置快慢兩個指針膝舅，fast, slow fast一次前進兩步嗡载，slow一次前進一步，
兩指針會相遇于6號節(jié)點铸史，設第一個節(jié)點到入環(huán)節(jié)點的距離為M=[0->2],
設入環(huán)口到相遇點的距離為N=[2->6]鼻疮，
設相遇點到入環(huán)口的距離為K=[6->2],
當fast，和slow相遇的時候琳轿，fast經(jīng)過的節(jié)點是slow的兩倍判沟，
設slow經(jīng)過的節(jié)點數(shù)為S，得S=M+N ,2S=M+N+K+N崭篡，
可知 M=K,此時讓slow回到第一個節(jié)點挪哄，fast處于第一次相遇的節(jié)點，
此時slow從第一個節(jié)點出發(fā)琉闪，因為M=K迹炼，所以fast，和slow會在入環(huán)口第二次相遇颠毙，得到要求的節(jié)點斯入。

public ListNode detectCycle(ListNode head)
    {
        if(head==null)
        return head;
        // 步驟一：使用快慢指針判斷鏈表是否有環(huán),必須快慢指針為同一起跑線
        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;
            }
        }

        // 步驟二：若有環(huán)，找到入環(huán)開始的節(jié)點
        if (hasCycle)
        {
            ListNode q = head;
            while (slow!= q)
            {
                slow = slow.next;
                q = q.next;
            }
            return q;
        } else
            return null;
    }

返回鏈表倒數(shù)第n個節(jié)點

快慢指針蛀蜜，一目了然

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

刪除鏈表倒數(shù)第n個節(jié)點

• 快慢指針刻两，quick先走n步，然后兩指針一起走滴某，quick.next為空磅摹，則slow.next為找到的倒數(shù)第n個結(jié)點滋迈，讓slow結(jié)點指向它的下一個節(jié)點

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

合并兩個有序鏈表

• 關鍵點：有序
• 引入輔助頭結(jié)點，因為要動態(tài)判斷第一個節(jié)點是哪個鏈表的户誓，然后保證兩鏈表不為空的情況下饼灿，總是讓指針指向下一個較小的節(jié)點，同時所在鏈表表頭更新到下一個節(jié)點帝美，退出循環(huán)碍彭，讓指針直接指向不為空的鏈表的頭結(jié)點

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)
        {
//  指針指向下一個較小的節(jié)點，同時所在鏈表表頭更新到下一個節(jié)點
            if(l1.val<=l2.val)
            {
                temp.next=l1;
                temp=temp.next;
                l1=l1.next;
            }
            else {
                temp.next = l2;
                temp=temp.next;
                l2 = l2.next;
            }
        }
// 指針直接指向不為空的鏈表的頭結(jié)點
        temp.next=l1==null?l2:l1;
        return dhead.next;
    }

反轉(zhuǎn)鏈表

@迭代

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之后鏈表反轉(zhuǎn)
        while(slow!=null)
        {
            ListNode next=slow.next;
            slow.next=pre;
            pre=slow;
            slow=next;

        }
        //3.前后鏈表進行比較硕旗，注意若為奇數(shù)鏈表，多1一個節(jié)點女责，然而并不影響判斷回文
        while (head!=null&&pre!=null)
        {
            if(head.val!=pre.val)
                return false;
            head=head.next;
            pre=pre.next;
        }
        return true;
    }

@數(shù)組緩存

• 單鏈表只能沿一個方向遍歷漆枚，可以借用一個輔助數(shù)組，將鏈表節(jié)點拷貝到數(shù)組中抵知， 然后在數(shù)組中雙指針檢查墙基，空間復雜度為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、拷貝到數(shù)組
        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;
    }

@棧

• 回文鏈表的特性：由前往后遍歷與由后往前遍歷的結(jié)果一樣
• 可以用棧保存由前往后遍歷的結(jié)果残制，再讓棧彈出節(jié)點與原鏈表的節(jié)點進行一 一 判斷

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

＠一

• 設交集鏈表長c,鏈表1除交集的長度為a，鏈表2除交集的長度為b掖疮，有a + c + b = b + c + a

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

@二

• 笨方法： 算出兩鏈表各自長度初茶，算差值n，鏈表長的先走n步,然后一起走

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

刪除排序鏈表中的重復元素

• 判斷當前節(jié)點與下一節(jié)點的值是否相同浊闪，相同則保存當前節(jié)點cur恼布，進入循環(huán)，一直到下一個不同值的節(jié)點搁宾，讓cur指向下一個不同值的節(jié)點

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

兩兩交換鏈表中的節(jié)點

• @遞歸

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