链表解题

2020-04-17

关于链表的解题

LeetCode 147、对链表进行插入排序 https://leetcode-cn.com/problems/insertion-sort-list/

参见前文对普通数组的插入排序，这里又有对链表的插入排序。

实际上实质是一样的，比较前后大小，然后交换位置。

在这里我们引入一个虚拟头节点(dummynode)，使用该节点的好处就是我们不用考虑头节点是不是为空，这些繁杂的边界情况。引入dummy，可以为我们省去很多麻烦.

在这里我们引入了两个指针，其实双指针在解决链表问题时也非常方便.

其实插入排序就是比较当插入新元素时，与前一个元素进行比较，如果此时新元素>前一个元素，即是有序的。此时我们只需要继续插入元素即可。
如果此时新元素<前一个元素，我们就需要找一个合适的位置将其插入。

class Solution {
    public ListNode insertionSortList(ListNode head) {
           ListNode dummy=new ListNode(0);
            dummy.next=head;
            //初始化两个指针
           ListNode pre=dummy;
           ListNode cur=head;
           ListNode temp=null;
           while(cur!=null&&cur.next!=null){
               //将cur.next暂存
               temp=cur.next;
               if(cur.val<=cur.next.val){
                   //是有序的
                   cur=cur.next;
               }else{
                   //表示前一个元素大于后面这个元素
                   //先将后面这个元素删除
                   cur.next=cur.next.next;
                   pre=dummy;
                   //找合适的位置插入元素
                   while(pre.next.val<=temp.val){
                       //表示没有到合适的位置
                       pre=pre.next;
                   }
                   temp.next=pre.next;
                   pre.next=temp;
               }
           }
           return dummy.next;
    }
}

LeetCode141、环形链表 https://leetcode-cn.com/problems/linked-list-cycle/

还是利用双指针思想，这里我们利用到一个快慢指针的方法。

想象一下我们在操场上跑步，跑的快的人和跑的慢的人，如果假设他们一直跑下去。那么他们一定会在某个时刻相遇，在第一次相遇这个时刻，跑的快的正好比跑的慢的多跑一圈。

那么这个环形链表也是同样的，我们让快指针每次走两步，慢指针每次走一步。如果链表中有环的话，那么快指针与慢指针一定会相遇。

同样的，我们还是引入一个dummynode,这样为我们省去很多麻烦.

public class Solution {
    public boolean hasCycle(ListNode head) {
    
        //快慢指针
        ListNode fast=head;
        ListNode slow=head;
      
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
          //如果相遇
            if(slow==fast)
            return true;
        }
        return false;
    }
}

LeetCode 142、环形链表二 https://leetcode-cn.com/problems/linked-list-cycle-ii/

此题是在上一题的基础上，如果有环的话，要返回环的位置。

我们假设环的长度为m+n,并且快慢指针在相遇的位置为m.假设头节点到环开始的距离为a。那么慢指针此时应该走了a+m。快指针走了a+n+2m，并且二者的速度分别为v和2v，且在相等的时间内，这时候我们就可以列出一个等式.

(a+m)/v=(a+2m+n)/2v. 通过这个等式，我们求的a=n.这是一个非常有用的信息.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
         ListNode fast=head;
         ListNode slow=head;

         while(fast!=null&&fast.next!=null){
             fast=fast.next.next;
             slow=slow.next;
             if(fast==slow){
                 //有环
               //即当快指针与慢指针相遇时，我们重新设置一个指针。和慢指针同样每次走一步
               //当二者相遇的时候，即a=n,此时新指针的位置即代表环的尾部连接第几个节点
                 ListNode temp=head;
                 while(slow!=temp){
                     temp=temp.next;
                     slow=slow.next;
                     //二者相遇，temp所在位置就是环的位置
                   
                 }
                  return temp;
             }
         }
         return null;
    }
}

LeetCode 92、反转链表二 https://leetcode-cn.com/problems/reverse-linked-list-ii/

此题是之前反转链表的升级版，有了上面一题的基础，这个题应该有一定的思路了。

由于这里是反转由m-n的节点，我们首先要定位到m位置的前一个节点

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
      ListNode dummy=new ListNode(0);
      dummy.next=head;
      ListNode pre=dummy;
      //先定位到待反转头节点的前一个节点
      for(int i=1;i<m;i++){
          //此时pre的下一个节点就是待反转的头节点
          pre=pre.next;
      }
        head=pre.next;
      for(int i=m;i<n;i++){
          //跟之前反转链表的操作一样
        
          ListNode rev=head.next;
          head.next=head.next.next;
          rev.next=pre.next;
          pre.next=rev;
      }
    return dummy.next;
    }
}

本思路是参照之前反转链表一，接下来提供另外一种思路。

由于题目需要反转，我们很容易联想到栈这一数据结构，栈具有后进先出的性质。我们完全可以先把节点值存进栈中，然后再取出，完成反转操作。

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
           Stack<Integer>stack=new Stack<>();
           int i=0;
           
          ListNode temp=head;
          //入栈
          while(temp!=null){
              i++;
              if(i>=m&&i<=n){
                  stack.push(temp.val);
              }
               temp=temp.next;
          }
          //出栈
          i=0;
          temp=head;
          while(head!=null){
              i++;
              if(i>=m&&i<=n){
                 head.val= stack.pop();
              }
              head=head.next;
          }
          return temp;
    }   
}

上述解法的巧妙之处在于，我们避开了链表中那些繁杂的指向操作，有时候因为那些连接的操作，导致我们头晕，但是栈的使用也只是在特定的情况下。