【leetcode】leetcode 刷题 笔记 （不定期更新）

237.Delete Node in a Linked List

题目要求只给定链表中一个节点的前提下，删除该节点。注意这里题目并没有给出对链表的引用，因而我们无法遍历链表得到前驱。有一个思路确实很好，它并不是删除链表的节点，而是把该节点的内容改为下一个节点的内容，把该节点的指针给为下一个节点的指针，相当于复制了下一个节点的内容然后删除下一个节点。

思考：这个思路在只有单链表的前提下确实无懈可击，不过不但这个链表被运用到实际应用中会有问题产生，因为应用中的实例可能会持有链表节点的引用，这种删除方式会导致引用发生错误，比如原本持有3的引用，正常来看，一旦删除3，就应该持有null才对，但是上述做法却让其持有了4的引用，反而原本持有4的引用的对象持有了null的引用，这是一个弊端。

234.Palindrome Linked List

Palindrome意思是回文，这个题目给出了判定回文的思路，即同时从前和从后遍历，比较两端的元素，只要有一次不同，就返回false，循环结束返回true。

（1）   这里还涉及如何反转一个链表，要设置next和pre指针，当遍历到p时，要改变它的next为pre，但是这样会丢掉原本链表的顺序，因此要用next先记录p的next，最后设置pre为p，p为之前保存的next

（2）   如何找到链表的中间元素？设置slow和fast两个指针，每一次迭代，slow设为下一个，fast设为下两个。直到fast为null或者fast.next为null为止。

按照上述解法得到的右侧链表含有较多的元素（奇数情况），然后把右侧反转后，右侧含有较少的元素（偶数情况，奇数反而相同，因为中间的元素被两边共享），因此，在最后双向遍历时，应当使用右侧链表的头指针为条件。画个图就很清楚了。

public class ListNode {

  private ListNode next;
  private int data;

  public ListNode(int data){
    this.data = data;
  }
}


public class Solution {

  public boolean isPalindrome(ListNode head){
    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.getNext() != null){
      slow = slow.getNext();
      fast = fast.getNext().getNext();
    }
    //右侧更少
    ListNode back = reverse(slow);
    while(back != null){
      if (back.getData() != head.getData()) {
        return false;
      }
      back = back.getNext();
      head = head.getNext();
    }
    return true;
  }
  
  public ListNode reverse(ListNode head){
    ListNode p = head;
    ListNode pre = null, next = null;
    while(p != null){
      next = p.getNext();
      p.setNext(pre);
      pre = p;
      p = next;
    }
    return pre;
  }
}

203.Remove Linked List Elements

链表中的删除操作，首先很重要一点是如果要删除头结点，我们在函数中是无法实现的，因为函数参数中的head是函数栈中对于调用处的真正head引用的拷贝，我们在函数中改变对head的赋值，并不能改变调用处head的赋值，唯一的解决办法就是让函数返回一个新的head，然后调用结束之后更新head。

思路：因为删除操作在单链表中必须得到前一个元素，因此遍历时只能检查下一个元素的值是否相等。While循环的条件是下一个元素是否为空。如果相等，修改next引用，否则，遍历继续。

这样的实现有一点需要注意，就是头结点无法检测，因为我们总是检测下一个元素是否相等，因此在上述循环之前，我们必须先对头节点检测，只要head相等，那么head后移。然后再进行上面的while循环，这样上面的while循环条件不仅要有itr.next!=null还要有itr!=null，因为对head检测结束，head可能为null。

public ListNode remove(ListNode head, int value){
    while(head != null && head.getData() == value){
      head = head.getNext();
    }
    ListNode p = head;
    while(p != null && p.getNext() != null){
      if (p.getNext().getData() == value) {
        p.setNext(p.getNext().getNext());
      }else {
        p = p.getNext();
      }
    }
    return head;
  }

那么为什么同样是检测下一个是否等于value，head处于后面的处理必须分开？因为head是对引用赋值，而后面是对引用指向的元素的属性赋值。因此在while循环内部的处理逻辑完全不同。即要修改链表元素的next域时，head和后面的操作不同。Head是要后移，而后面的元素是赋值。

这里还有一种思路，就是新建一个dummy节点，其数据域一定不等于value，比如value+1。然后再进行上面的while循环，这样做的好处就是省去了头结点的处理，用空间换时间。使得while循环 内部的处理逻辑相同。

public ListNode remove1(ListNode head, int value){
    ListNode dummy = new ListNode(value + 1);
    dummy.setNext(head);
    ListNode p = dummy;
    while(p != null && p.getNext() != null){
      if (p.getNext().getData() == value) {
        p.setNext(p.getNext().getNext());
      }else {
        p = p.getNext();
      }
    }
    return dummy.getNext();
  }

160.Intersection of Two Linked Lists

这道题目有一个要求，那就是intersecting的一个或者多个元素之后，两个链表的长度必须相同。否则下述算法达不到效果。在上述前提下，这个算法在找相同元素的时候只用了On的复杂度，正常情况下我们需要On2的复杂度。如果存在，那么返回非空，否则，当a==b时，均为null，会返回null。

public ListNode firstIntersect(ListNode headA, ListNode headB){
    ListNode a = headA;
    ListNode b = headB;
    
    while(a != b){
      a = a == null?headB:a.getNext();
      b = b == null?headA:b.getNext();
    }
    return a;
  }

141.Linked List Cycle

这是快慢指针在链表中的两一个应用，除了找中间元素意外，还可判断是否有环路。Fast指针的条件是非空和下一个非空，那么结束时，要么null要么最后一个。

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

83.Remove Duplicates from Sorted List

234已经涉及。比较简单，主要是一个while循环，然后循环内部比较当前与下一个，因此，最后一个元素肯定在前驱就会被处理，所以循环条件可以是next与当前均不为null。循环体内部处理就是一个if，如果不等，就迭代至下一个，反之，进行next拷贝。

不过这个题目给出了一个删除链表中重复元素的方法，就是先排序，然后按照上面方法，复杂度是nlogn。

注意上述方法的前提是排序。

public ListNode deleteDuplicates(ListNode head) {
        ListNode p = head;
        while(p != null && p.getNext() != null){
            if (p.getData() != p.getNext().getData()) {
                p = p.getNext();
            }else {
                p.setNext(p.getNext().getNext());
            }
        }
        return head;
    }

24.Swap Nodes in Pairs

首先把head指针调成第二个元素，然后是一个while循环，不断调整相邻的两个元素。这里还必须设置一个pre引用，因为while内的处理逻辑会用到之前一次迭代的元素，这个与reverse操作比较类似，也是一个注意点，就是说只要需要用到之前一次迭代的元素，那么就用一个pre来记录。

public ListNode swapPairs(ListNode head) {
    ListNode p = head;
      if (head != null && head.getNext() != null) {
      head = head.getNext();
    }
      ListNode pre = null;
      while(p != null && p.getNext() != null){
        ListNode p1 = p.getNext();
        p.setNext(p1.getNext());
        p1.setNext(p);
        if (pre != null) {
          pre.setNext(p1);
      }
        pre = p;
        p = p.getNext();
      }
      return head;
  }