206.反转链表

方法1：使用迭代法，前后两个指针开始遍历

class Solution {
  public ListNode reverseList(ListNode head) {
      if (head == null) return head;
      ListNode newHead = null;
      ListNode cur = head;
      while (cur != null){
          ListNode next = cur.next;
          cur.next = newHead;
          newHead = cur;
          cur = next;
      }
      return behind;
  }
}

方法2：递归法，将链表分为两部分，第一部分是一个结点，第二部分就是剩下的链表，对第二部分使用递归方法，最后注意递归的终止条件即可。

class Solution {
  public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) return head;
      ListNode tail = head.next;
      ListNode node = reverseList(head.next);
      tail.next = head;
      head.next = null;
      return node;
  }
}

方法3：头插法

//头插法
      public ListNode reverseList(ListNode head) {
          ListNode dummyNode = new ListNode(-1);
          while (head != null) {
              ListNode next = head.next;
              head.next = dummyNode.next;
              dummyNode.next = head;
              head = next;
          }
          return dummyNode.next;
      }

92.反转链表 II

这道题跟206.反转链表题差不多，只不过在反转前

首先要找到反转的起点
然后反转一部分链表
最后把头和尾连接起来就行。

        //Date:2020-10-05 15:25:36
        //执行耗时:0 ms,击败了100.00% 的Java用户
        public ListNode reverseBetween(ListNode head, int m, int n) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode preM = dummy;
            for (int i = 0; i < m - 1; i++) {
                preM = preM.next;
            }
            //反转起点
            ListNode cur = preM.next;
            ListNode newHead = null;
            for (int i = m; i <= n; i++) {
                ListNode next = cur.next;
                cur.next = newHead;
                newHead = cur;
                cur = next;
            }
            //尾指针拼接
            preM.next.next = cur;
            //头拼接
            preM.next = newHead;
            return dummy.next;
        }

21.合并两个有序链表

203. 移除链表元素

这道题确实简单，两个指针依次遍历即可。主要关注

虚拟头结点的运用

class Solution {
  public ListNode removeElements(ListNode head, int val) {
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      ListNode behind = dummy, cur = head;
      while (cur != null) {
          if (cur.val == val){
              behind.next = cur.next;
              cur.next = null;
              cur = behind.next;
          } else {
              behind = cur;
              cur = cur.next;
          }
      }
      return dummy.next;
  }
}

2. 两数相加

思路：一条链表一个指针，依次计算指针的和，每次计算生成一个新结点，注意一下进位，当两个指针都为null时说明相加过程结束，但是还要注意最后一次可能有进位。

class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode res = new ListNode(-1);
      ListNode cur = res, i = l1, j = l2;
      int append = 0;
      while (i != null || j != null) {
          int v1 = i != null ? i.val : 0;
          int v2 = j != null ? j.val : 0;
          int val = (v1 + v2 + append) % 10;
          append = (v1 + v2 + append) / 10; 
          cur.next = new ListNode(val);
          cur = cur.next;
          i = i != null ? i.next : null;
          j = j != null ? j.next : null;
      }
      if (append != 0) {
          cur.next = new ListNode(append);
      }
      return res.next;
  }
}

160. 相交链表

在两个链表的头结点分别设定一个移动指针，要想让它们在交汇处相遇，只能让它们走过的路程一样，所以在走完自己的路后，再走一下对方走过的路，后台灵光一现，写下来代码。哈哈

public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode l1 = headA, l2 = headB;
      while (l1 != l2) {
          l1 = l1 != null ? l1.next : headB;
          l2 = l2 != null ? l2.next : headA;
      }
      return l1;
  }
}

86. 分隔链表

思路:新建两个dummy节点，还有两个指向尾结点的指针，再来个遍历指针遍历输入链表，如果小于x就挂到dummy1下，否则挂到dummy2下。。。感觉这题没有中等难度吧。。

class Solution {
  public ListNode partition(ListNode head, int x) {
      ListNode dummy1 = new ListNode(-1), dummy2 = new ListNode(-2);
      ListNode cur = head, l1 = dummy1, l2 = dummy2;
      while (cur != null) {
          if (cur.val < x) {
              l1.next = cur;
              l1 = l1.next;
          } else {
              l2.next = cur;
              l2 = l2.next;
          }
          cur = cur.next;
      }
      l1.next = dummy2.next;
      l2.next = null;
      return dummy1.next;
  }
}

234. 回文链表

这道题虽说是简单题，但是感觉不是那么简单，主要有一个空间复杂度的要求。
如果没有空间复杂度要求可以新建一个反转链表，然后两个链表依次对比就ok了。
在空间复杂度的条件下的方案可以如下:

快慢指针找到中间节点(中间节点:下半链表的前一个节点），这个代码眼睛闭起来也要默写出来😂。
反转后面一段链表（这个也是必须会的）

两个链表依次比较

class Solution {
  public boolean isPalindrome(ListNode head) {
      if (head == null || head.next == null) return true;
      ListNode l1 = head;
      ListNode mid = findMidNode(head);
      ListNode l2 = reverse(mid.next);

      while (l2 != null) {
          if (l1.val != l2.val) return false;
          l1 = l1.next;
          l2 = l2.next;
      }
      return true;
  }
  // 1->2->3  return 2
  // 1->2->3->4 return 2
  private ListNode findMidNode(ListNode head) {
      ListNode slow = head, fast = head;
      while (fast.next != null && fast.next.next != null) {
          fast = fast.next.next;
          slow = slow.next;
      }
      return slow;
  }
  private ListNode reverse(ListNode node) {
      ListNode pre = null;
      while (node != null) {
          ListNode next = node.next;
          node.next = pre;
          pre = node;
          node = next;
      }
      return pre;
  }
}

138. 复制带随机指针的链表

这道题的主要难点是在如何复制random指针，在对原链表进行遍历-复制时，random指针指向的节点很随意，在复制的链表中无法定位到，所以要想个办法在任意时候根据原结点都能找到其复制节点，自然想到用map，其实map的本质也就是一个指针的功能，即k指向v。

public Node copyRandomList(Node head) {
  if (head == null) return null;
  Node cur = head;
  Map<Node, Node> map = new HashMap<>();
  while (cur != null) {
      map.put(cur, new Node(cur.val));
      cur = cur.next;
  }

  cur = head;
  while (cur != null) {
      map.get(cur).next = map.get(cur.next);
      map.get(cur).random = map.get(cur.random);
      cur = cur.next;
  }
  return map.get(head);
}

如果要求空间复杂度是O(1)呢？有点难了，但是上面说了本质上，map本质就是多了一个指针而已。

class Solution {
  public Node copyRandomList(Node head) {
      if (head == null) return null;
      //3 step:拷贝、调整指针、解绑
      Node  cur = head;
      while (cur != null) {
          Node newNode = new Node(cur.val);
          newNode.next = cur.next;
          cur.next = newNode;
          cur = newNode.next;
      }

      cur = head;
      while (cur != null) {
          Node random = cur.random;
          if (random == null){
              cur.next.random = null;
          } else {
              cur.next.random = random.next;
          }
          cur = cur.next.next; 
      }
      cur = head;
      Node newHead = head.next;
      while (cur != null && cur.next != null) {
          Node next = cur.next; 
          cur.next = next.next;
          cur = next;
      }
      return newHead;
  }
}

25. K 个一组翻转链表

这道题其实思路并不难，主要是要考虑细节，指针如何分配，最后一段的节点个数小于k时如何处理。观察下图：
设定一个dummy节点作为上一端的尾结点，需要反转链表的起始节点start，尾结点end，下一段的起始节点next。大概分为3步

确定起始end节点，如果不为null时反转，否则可以结束了。
反转start和end之间的链表

调整preTail指针，start指针状态。

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
      if (head == null || k == 1) return head;
      ListNode dummy = new ListNode(-1);
      ListNode preTail = dummy, start = head;
      while (start != null) {
          ListNode end = start, next = null;
          for (int i = 0; i < k - 1 && end != null; i++) {
              end = end.next;
          }
          if (end == null) {
              //最后一段结点数没有k个，不需要反转了，结束。
              preTail.next = start;
              return dummy.next;
          }
          next = end.next;//准备下一段的指针
          end.next = null;//为了反转设置null
          reverse(start);
          preTail.next = end;//上一段的尾结点和当前头结点连接
          preTail = start;//调整尾结点
          start = next;//下一段迭代
      }
      return dummy.next;

  }
  private void reverse(ListNode start) {
      ListNode pre = null, cur = start;
      while (cur != null) {
          ListNode next = cur.next;
          cur.next = pre;
          pre = cur;
          cur = next;
      }
  }
}

其实每反转一段链表后，可以把当前链表的尾结点和下一段链表先连接起来，这样保证一次循环后链表是完整的，返回时就可以直接返回了。

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
      if (head == null || k == 1) return head;
      ListNode dummy = new ListNode(-1);
      dummy.next = head;// +
      ListNode preTail = dummy, start = head;
      while (start != null) {
          ListNode end = start, next = null;
          for (int i = 0; i < k - 1 && end != null; i++) {
              end = end.next;
          }
          if (end == null) break ;

          next = end.next;
          end.next = null;
          reverse(start);
          start.next = next;//增加的这一行，这样12行就可以直接返回了。
          preTail.next = end;
          preTail = start;
          start = next;
      }
      return dummy.next;

  }
  private void reverse(ListNode start) {
      ListNode pre = null, cur = start;
      while (cur != null) {
          ListNode next = cur.next;
          cur.next = pre;
          pre = cur;
          cur = next;
      }
  }
}

24. 两两交换链表中的节点

如果理解25题的思想，这道题就是切菜了，看图就行咯

class Solution {
  public ListNode swapPairs(ListNode head) {
      if (head == null || head.next == null) return head; 
      ListNode dummy = new ListNode(-1);
      ListNode preTail = dummy, cur = head;
      preTail.next = head;
      while (cur != null && cur.next != null) {
          preTail.next = cur.next;
          ListNode next = cur.next.next;
          cur.next.next = cur;
          cur.next = next;//这个指针补上，最后一端如果是单个节点皆可以直接返回了
          preTail = cur;
          cur = next;
      }
      return dummy.next;
  }
}

237. 删除链表中的节点

这道题的输入没有head节点，只给了待删除的node节点，所以常规删除节点的思维没法搞定，感觉是有点脑筋急转弯：将待删除节点的下一个节点的值覆盖删除节点的值，将下一个节点删掉。呵呵

class Solution {
  public void deleteNode(ListNode node) {
      if (node == null || node.next == null) return;
      node.val =node.next.val;
      node.next = node.next.next;
  }
}

141. 环形链表

思路：

如果对空间没有要求的话，可以使用一个Hash表，记录走过的路径，后面每遍历一个结点，就查询其next指针是否在Hash表里。

如果是用O(1)空间复杂度的话，就要使用快慢指针了，快指针每次跳两个，慢指针每次跳一个，所以如果有环结点的话，快指针和慢指针的差距每次都会缩短1个结点，后面总会相遇。

public class Solution {
  public boolean hasCycle(ListNode head) {
      if (head == null || head.next == null) return false;
      ListNode slow = head, fast = head;
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
          if (slow == fast) return true;
      }
      return false;
  }
}

21. 合并两个有序链表

类似于归并排序，主要是终止条件的选择，选择l1 != null && l2 != null要比l1 != null || l2 !=null代码看起来简单一点。

class Solution {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode dummy = new ListNode(-1), tail = dummy;
      while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
              tail.next = l1;
              l1 = l1.next;
          } else {
              tail.next = l2;
              l2 = l2.next;
          }
          tail = tail.next;
      }
      tail.next = l1 == null ? l2 : l1;
      return dummy.next;
  }
}

也可以使用递归法去解决

class Solution {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      if (l1 == null) {
          return l2;
      } else if (l2 == null) {
          return l1;
      }else if (l1.val < l2.val) {
          l1.next = mergeTwoLists(l1.next, l2);
          return l1;
      }else {
          l2.next = mergeTwoLists(l1, l2.next);
          return l2;
      }
  }
}

23. 合并K个升序链表

原始思路

初始思路：每次比较数组中所有的链表头中元素，选择一个最小的挂到新的节点上，然后将该位置的链表头更新为下一个，直到数组中所有的元素都是null，这个思路比较清晰，但是时间复杂度是O(n * n)

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
      ListNode dummy = new ListNode(-1), tail = dummy;
      while (!isEmpty(lists)){
          int minIndex = findMinListNode(lists);
          tail.next = lists[minIndex];
          tail = tail.next;
          lists[minIndex] = lists[minIndex].next;
      }
      return dummy.next;
  }
  private boolean isEmpty(ListNode[] lists) {
      for (int i = 0; i < lists.length; i++) {
          if (lists[i] != null) return false;
      }
      return true;
  }
  private int findMinListNode(ListNode[] lists) {
      int minIndex = 0, minValue = Integer.MAX_VALUE;
      for (int i = 0; i < lists.length; i++) {
          if (lists[i] != null && lists[i].val <= minValue) {
              minValue = lists[i].val;
              minIndex = i;
          }
      }
      return minIndex;
  }
}

分治法

其实可以采用归并排序的思想，转化成两个有序链表的排序。

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
      if (lists == null || lists.length == 0) return null;
      return merge(lists, 0, lists.length - 1);
  }
  private ListNode merge(ListNode[] lists, int left, int right) {
      if (left == right) return lists[left];
      int mid = left + (right - left) / 2;
      ListNode l1 = merge(lists, left, mid);
      ListNode l2 = merge(lists, mid + 1, right);
      return mergeTwoList(l1, l2);
  }
  private ListNode mergeTwoList(ListNode l1, ListNode l2) {
      ListNode dummy = new ListNode(-1), tail = dummy;
      while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
              tail.next = l1;
              l1 = l1.next;
          } else {
              tail.next = l2;
              l2 = l2.next;
          }
          tail = tail.next;
      }
      tail.next = l1 == null ? l2 : l1;
      return dummy.next;
  }
}

146. LRU 缓存机制

```java class LRUCache { HashMap map; Node head; Node tail; int capacity; public LRUCache(int capacity) {

  this.capacity = capacity;
  map = new HashMap();
  head = new Node(-1, -1);
  tail = new Node(-1, -1);
  head.next = tail;
  tail.pre = head;

}

public int get(int key) {

  Node node = map.get(key);
  if (node == null) return -1;
  put(key, node.value);//这边正好利用put方法将元素放到表头
  return node.value;

}

public void put(int key, int value) {

  Node node = new Node(key, value);
  addFirst(node);
  if (map.containsKey(key)) {
      Node old = map.get(key);
      remove(old);
  }
  map.put(key, node);
  if (map.size() > capacity) {
      Node toRemove = tail.pre;
      remove(toRemove);
      map.remove(toRemove.key);
  }

} private void addFirst(Node node) {

  node.next = head.next;
  head.next.pre = node;

  head.next = node;
  node.pre = head;

} private void remove(Node node) {

  node.pre.next = node.next;
  node.next.pre = node.pre;

  node.next = null;
  node.pre = null;

} class Node {

  Node (int key, int value) {
      this.key = key;
      this.value = value;
  }
  int key;
  int value;
  Node pre;
  Node next;

} }

/**

Your LRUCache object will be instantiated and called as such:
LRUCache obj = new LRUCache(capacity);
int param_1 = obj.get(key);

obj.put(key,value); */

<a name="Szyby"></a>
# [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
![image.png](https://cdn.nlark.com/yuque/0/2021/png/1787610/1614691378206-a21caf10-b959-41bc-b81a-92a536105f39.png#align=left&display=inline&height=410&margin=%5Bobject%20Object%5D&name=image.png&originHeight=820&originWidth=882&size=147957&status=done&style=none&width=441)
```java
class Solution {
 public ListNode removeNthFromEnd(ListNode head, int n) {
     ListNode dummy = new ListNode(-1);
     dummy.next = head;
     ListNode p1 = dummy, p2 = dummy;
     for (int i = 0; i < n && p1 != null; i++) {
         p1 = p1.next;
     }
     if (p1 == null) return dummy.next;

     while (p1.next != null) {
         p1 = p1.next;
         p2 = p2.next;
     }
     p2.next = p2.next.next;
     return dummy.next;
 }
}

leetCode

链表(一)