算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題

這篇具有很好參考價(jià)值的文章主要介紹了算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

內(nèi)容

算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

鏈表的定義

         class ListNode {
            int val;
            ListNode next;  
            
            ListNode(int val) {
                this.val = val;
            }
        }

找到兩個(gè)鏈表第一個(gè)公共子節(jié)點(diǎn)

劍指office 52題
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

public class 鏈表相交 {
    class Solution {
        //1. 哈希集
/*        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            Set<ListNode> set = new HashSet<>();
            while (headA != null) {
                set.add(headA);
                headA = headA.next;
            }
            while (headB != null) {
                if (set.contains(headB)) {
                    return headB;
                }
                headB = headB.next;
            }
            return headB;
        }*/

        //2. 棧
             /*   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
                    Stack<ListNode> a=new Stack<>();
                    Stack<ListNode> b=new Stack<>();
                    ListNode pre=null;
                    while(headA!=null){
                        a.push(headA);
                        headA=headA.next;
                    }
                    while(headB!=null){
                        b.push(headB);
                        headB=headB.next;
                    }
                    while(a.size()>0 &&b.size()>0){
                        if(a.peek()==b.peek()){
                            pre=a.pop();
                            b.pop();
                        }else{
                            break;
                        }
                    }
                    return pre;
        }
*/

        //3.雙指針
     /*   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
              if ( headA== null ||  headB== null) {
            return null;
        }
        ListNode p1 =headA ;
        ListNode p2 =headB ;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            //不加上，如果沒(méi)有相同結(jié)點(diǎn)就死循環(huán)了
            if (p1 != p2) {
                if (p1 == null) {
                    p1 =headB ;
                }
                if (p2 == null) {
                    p2 =headA ;
                }
            }
        }
        return p1;

    }*/

        //4. 差和雙指針
        //因?yàn)楣仓粫?huì)出現(xiàn)在較短的鏈表中，所以讓它們一起開(kāi)始遍歷;
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode pre1 = headA;
            ListNode pre2 = headB;
            int len1 = 0, len2 = 0;
            while (pre1 != null) {
                len1++;
                pre1 = pre1.next;
            }
            while (pre2 != null) {
                len2++;
                pre2 = pre2.next;
            }
            //一樣長(zhǎng)的無(wú)變化
            int sub = len1 > len2 ? len1 - len2 : len2 - len1;
            pre1 = headA;
            pre2 = headB;
            if (len1 > len2) {
                //長(zhǎng)的先走sub步
                for (int i = 0; i < sub; i++) {
                    pre1 = pre1.next;
                }
            }
            if (len2 > len1) {
                //長(zhǎng)的先走sub步
                for (int i = 0; i < sub; i++) {
                    pre2 = pre2.next;
                }
            }
            while (pre1 != pre2) {
                pre1 = pre1.next;
                pre2 = pre2.next;
            }
            return pre1;

        }
    }
}

判斷鏈表是否為回文序列

LeetCode234題
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

public class 回文鏈表 {
    class Solution {
        //1. 棧
    /*
    public boolean isPalindrome(ListNode head) {
   ListNode temp=head;
   Stack<Integer> stack=new Stack<>();
   int len=0;
   while(temp!=null){
       stack.push(temp.val);
       temp=temp.next;
       len++;
   }
   while(stack.size()>=len/2 &&head!=null){
       if(head.val!=stack.pop()){
return false;
       }
       head=head.next;
   }
   return true;
    }
    */

        //2.快慢指針

        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            //slow和fast是快慢指針，slow到一半，fast到結(jié)尾了，prepre指針作用是不斷翻轉(zhuǎn)前一半的鏈表，pre最后會(huì)變成中間結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，因?yàn)橹虚g結(jié)點(diǎn)一定相同，然后處在中間的slow往右移到一個(gè)單位，就能開(kāi)始和pre指針的遍歷比較了。
            ListNode slow = head, fast = head;
            ListNode pre = head, prepre = null;
            while (fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
                pre.next = prepre;
                prepre = pre;
            }
            if (fast != null) {
                slow = slow.next;
            }
            while (pre != null && slow != null) {
                if (pre.val != slow.val) {
                    return false;
                }
                pre = pre.next;
                slow = slow.next;
            }
            return true;
        }

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

    }
}

合并兩個(gè)有序鏈表

LeetCode 21
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //方法1:
   /*     ListNode newHead = new ListNode(-1);
        ListNode res = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                newHead.next = list1;
                list1 = list1.next;
            } else if (list1.val > list2.val) {
                newHead.next = list2;
                list2 = list2.next;
            } else { //相等的情況，分別接兩個(gè)鏈
                newHead.next = list2;
                list2 = list2.next;
                newHead = newHead.next;
                newHead.next = list1;
                list1 = list1.next;
            }
            newHead = newHead.next;

        }
        while (list1 != null) {
            newHead.next = list1;
            list1 = list1.next;
            newHead = newHead.next;
        }
        while (list2 != null) {
            newHead.next = list2;
            list2 = list2.next;
            newHead = newHead.next;
        }
 /*       
 //最開(kāi)始沒(méi)有一點(diǎn)優(yōu)化的版本       
 /* ListNode pre=new ListNode(-1);
    ListNode res=pre;
    while(list1!=null ||list2!=null){
        if(list1!=null &&list2!=null){
            if(list1.val<list2.val){
                pre.next=list1;
                list1=list1.next;
            }else if(list1.val>list2.val){
                pre.next=list2;
                list2=list2.next;
            }else if(list1.val==list2.val){
             pre.next=list1;
                list1=list1.next;
                pre=pre.next;
                pre.next=list2;
                list2=list2.next;
            }
            pre=pre.next;
        }else if(list1==null &&list2!=null){
             pre.next=list2;
                list2=list2.next;
                pre=pre.next;
        }else if(list1!=null &&list2==null){
               pre.next=list1;
                list1=list1.next;
                pre=pre.next;
        }
    }  
    return res.next;*/


        //方法2:優(yōu)化方法1
  /*  ListNode l1=list1;
    ListNode l2=list2;
           ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 最多只有一個(gè)還未被合并完，直接接上去就行了,這是鏈表合并比數(shù)組合并方便的地方
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;   */

        //方法3:遞歸
        ListNode l1 = list1;
        ListNode l2 = list2;
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

合并K個(gè)升序鏈表

LeetCode 23

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoListsMoreSimple(res, list);
        }
        return res;
    }
        public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 最多只有一個(gè)還未被合并完，直接接上去就行了,這是鏈表合并比數(shù)組合并方便的地方
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

合并兩個(gè)鏈表

LeetCode 1669
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode pre1=list1;
        ListNode pre2=list1;
        ListNode pre3=list2;
        int i=0,j=0;
        //j<b 防止i==a-1，j==b時(shí)候，循環(huán)出不去了；
        while(pre1!=null &&pre2!=null &&j<b){
            //到a前面一個(gè)結(jié)點(diǎn)
          if(i!=a-1){
              pre1=pre1.next;
              i++;
          }
          //到b
          if(j!=b){
              pre2=pre2.next;
              j++;
          }
        }
        pre2=pre2.next;
        //到list2最后
        while(pre3.next!=null){
 pre3=pre3.next;
        }
        //鏈1尾鏈住2頭，鏈2尾接鏈1后半部分的頭
        pre1.next=list2;
        pre3.next=pre2;
        return list1;
    }
}

鏈表的中間結(jié)點(diǎn)

LeetCode 876
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    //快慢指針
    public ListNode middleNode(ListNode head) {
    ListNode pre1=head;
    ListNode pre2=head;
    while(pre2!=null && pre2.next!=null){
             pre1=pre1.next;
             pre2=pre2.next.next;
    }
    return pre1;
    }
}

鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

劍指 Offer 22
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    //假設(shè)有五個(gè)結(jié)點(diǎn)，找倒數(shù)第二個(gè)，那么它就是正數(shù)第四個(gè)結(jié)點(diǎn)，想達(dá)到這個(gè)目標(biāo)只需要走n-k步，也就是5-2=3步即可，因?yàn)樽叩阶詈竽莻€(gè)位置要n步，所以我讓快指針先走k步（2步），到達(dá)正數(shù)第三個(gè)位置，然后還有三步兩個(gè)一起走n-k步即可;
    public ListNode getKthFromEnd(ListNode head, int k) {
   ListNode pre1=head;
   ListNode pre2=head;
   while(pre1!=null&& k>0){
       pre1=pre1.next;
       k--;
   }
   while(pre1!=null){
       pre2=pre2.next;
       pre1=pre1.next;
   }
   return pre2;

    }
}

旋轉(zhuǎn)鏈表

LeetCode 61
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

//雙指針找到倒數(shù)第k個(gè)位置，分成123和45兩個(gè)序列，快指針先走k步，然后一起走，快指針到尾部時(shí)候，慢指針到了倒數(shù)第k個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，也就是3，將4賦值給res后，3指向null，快指針代表的5也指向了頭結(jié)點(diǎn)1，完成了旋轉(zhuǎn)，最后是45123;
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
 if (head == null || k == 0) {
            return head;
        }
        ListNode temp = head;
        ListNode fast = head;
        ListNode slow = head;
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        if (k % len == 0) {
            return temp;
        }
        while ((k % len) > 0) {
            k--;
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode res = slow.next;
        slow.next = null;
        fast.next = temp;
        return res;
    }
}

刪除指定結(jié)點(diǎn)

LeetCode 203
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    public ListNode removeElements(ListNode head, int val) {

//方法1:
//如果要?jiǎng)h除的值為val的是頭結(jié)點(diǎn),可能新的頭結(jié)點(diǎn)值也為val,題目要求
//刪除所有值為val的,所以使用while循環(huán);
while(head!=null && head.val==val){
    head=head.next;
}
if(head==null){
    return head;
}
ListNode prev=head;
while(prev.next!=null){
if(prev.next.val==val){
             prev.next=prev.next.next;
         }else{
             prev=prev.next;
         }
}
return head;

//方法2:虛擬頭結(jié)點(diǎn)
 /*    ListNode dNode=new ListNode(val-1);
     dNode.next=head;
     ListNode prev=dNode;
     //共用一個(gè)內(nèi)存了
     while(prev.next!=null){
         if(prev.next.val==val){
             prev.next=prev.next.next;
         }else{
             prev=prev.next;
         }
     }
     return dNode.next;  */
    }
}

刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

LeetCode 19
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    //方法1:雙指針,因?yàn)檫@次要?jiǎng)h倒數(shù)第k個(gè)，要找前一個(gè)，所以從虛擬結(jié)點(diǎn)開(kāi)始;
    //建立頭結(jié)點(diǎn)，方便刪除第一個(gè)結(jié)點(diǎn)
  /*  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre1=head; 
    ListNode pre3=new ListNode(0);
    pre3.next=head;
    ListNode pre2=pre3;
    while(pre1!=null && n>0){
     n--;
     pre1=pre1.next;
    }
     while(pre1!=null){
     pre2=pre2.next;
     pre1=pre1.next;
    }
    pre2.next=pre2.next.next;
    return pre3.next;
    }  */

    //方法2：利用棧
    public ListNode removeNthFromEnd(ListNode head, int n) {
 // ListNode pre1=head; 
    ListNode pre3=new ListNode(0);
    pre3.next=head;
    ListNode pre2=pre3;
    Stack<ListNode> stack=new Stack<>();
    while(pre2!=null){
        stack.push(pre2);
        pre2=pre2.next;
    }
    for(int i=0;i<n;i++){
        stack.pop();
    }
    //此時(shí)棧頂就是倒數(shù)第n個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
     pre2 = stack.peek();
pre2.next=pre2.next.next;
return pre3.next;
    }
}

刪除排序鏈表中的重復(fù)元素（保留一個(gè)）

LeetCode 83
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu)

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
          if(head==null){
              return head;
          }
          ListNode pre=head;
          while(pre.next!=null){
              if(pre.val==pre.next.val){
                  pre.next=pre.next.next;
              }else{
                  pre=pre.next;
              }
          }
          return head;
    }
}

刪除排序鏈表中的重復(fù)元素（重復(fù)元素都不要）

LeetCode 82
算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題,算法,鏈表,數(shù)據(jù)結(jié)構(gòu) 文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-630360.html

class Solution {
    //因?yàn)橛袆h頭結(jié)點(diǎn)的可能性,所以設(shè)置虛擬頭結(jié)點(diǎn)
    public ListNode deleteDuplicates(ListNode head) {
 ListNode pre=new ListNode(0);
 pre.next=head;
  ListNode cur=pre;
  while(cur.next!=null &&cur.next.next!=null){
      if(cur.next.val == cur.next.next.val){
          int x=cur.next.val;
          //這個(gè)while作用是一次性把重復(fù)的刪干凈
          while(cur.next!=null &&cur.next.val==x){
              cur.next=cur.next.next;
          }
          }else{
              cur=cur.next;
          }
      }
        return pre.next;
  }

    }

到了這里，關(guān)于算法通關(guān)村第一關(guān)——鏈表經(jīng)典問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！