LeetCode之链表

抽出一天时间把链表相关的题刷了一遍，总的来说链表的题总体难度还是不大的，巧妙使用快慢指针法和辅助头节点法，递归法，大部分链表问题都可以解决，但像环的检测用快慢指针去做还是很难想到的。

• 单链表反转 （206）

  import java.util.ArrayList;
  public class Solution {
      class ListNode {
          int val;
          ListNode next;

          ListNode(int x) {
              val = x;
          }
      }
      //头插法，迭代实现
      public ListNode reverseList(ListNode head) {
          ListNode newHead = new ListNode(-1);
          while (head != null) {
              ListNode next = head.next;
              head.next = newHead.next;
              newHead.next = head;
              head = next;
          }
          return newHead.next;
      }
      //    递归实现
      public ListNode reverseList2(ListNode head) {
          if (head == null || head.next == null) return head;
          ListNode next = head.next;
          ListNode node = reverseList2(next);
          next.next = head;
          head.next = null;
          return node;
      }
  }

• 链表中环的检测（141）

  import java.util.HashSet;
  public class Solution {
      class ListNode {
          int val;
          ListNode next;
  
          ListNode(int x) {
              val = x;
              next = null;
          }
      }
      //哈希表法空间复杂度为O(n)
      public boolean hasCycle(ListNode head) {
          HashSet<ListNode> nodes = new HashSet<>();
          while (head != null) {
  //            nodes.add(head);
  //            head = head.next;
  //            if (head != null && nodes.contains(head)) return true;
              if (nodes.contains(head)) return true;
              else nodes.add(head);
              head = head.next;
  
          }
          return false;
      }
      //    快慢指针法：空间复杂度为O(1)
      public boolean hasCycle2(ListNode head) {
          if (head == null || head.next == null) {
              return false;
          }
          ListNode slow = head;
          ListNode fast = head.next;
          while (slow != fast) {
              if (fast == null || fast.next == null) {
                  return false;
              }
              slow = slow.next;
              fast = fast.next.next;
          }
          return true;
      }
  }
  

• 两个有序的链表合并（21）

  public class Solution {
      class ListNode {
          int val;
          ListNode next;
  
          ListNode(int x) {
              val = x;
          }
      }
  
      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
          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;
          }
      }
  }
  

• 删除链表倒数第n个结点（19）

  public class Solution {
      class ListNode {
          int val;
          ListNode next;
  
          ListNode(int x) {
              val = x;
          }
      }
  //快慢指针+头节点辅助法
      public ListNode removeNthFromEnd(ListNode head, int n) {
          ListNode dummy = new ListNode(-1);
          dummy.next = head;
          ListNode fast = dummy;
          ListNode slow = dummy;
          for (int i = 0; i < n; i++) {
              fast = fast.next;
          }
          while (fast.next != null) {
              fast = fast.next;
              slow = slow.next;
          }
          slow.next = slow.next.next;
          return dummy.next;
      }
  }
  

• 求链表的中间结点 （876）

public class Solution {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
//快慢指针
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            if (fast.next == null) return slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}