知识点

LeetCode算法题

LeetCode算法题
1. 206.【反转链表】
  
  解题思路：
  
  使用迭代法进行反转。
2. 2.【两数相加】
  
  解题思路：
  
  利用迭代的方式，对两个链表进行迭代并对val进行相加。定义一个int值carry存储进位信息。
  
  最需要注意的是，两个链表如果最后相加后，还有进位的值，需要在迭代完成后再进行一次判断：
```
 if (carry > 0) {
     tail.next = new ListNode(carry);
 }
```
3. 21.【合并两个有序链表】
  
  解题思路：
  
  链表具有递归结构，因此大部分的链表题目先考虑递归解法。
  
  该题目可以理解为：两个链表中，较小的一个节点与剩下所有元素的合并。而我们可以用一个递归函数来表示这一个过程：如果 l1 或者 l2 一开始就是空链表，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
  
  最终，该递归函数为：
```
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

 if (l1 == null) {
     // l1元素都没有了，则将l2剩下的元素都返回回去取合并
     return l2;
 } else if (l2 == null) {
     // // l2元素都没有了，则将l1剩下的元素都返回回去取合并
     return l1;
 }

 if (l1.val < l2.val) {
     // l1当前元素小于l2当前元素，l1合并l1下面元素和l2的所有元素，然后返回
     l1.next = mergeTwoLists(l1.next, l2);
     return l1;
 } else {
     // l2当前元素小于l1当前元素，l2合并l2剩下元素和l1当前元素，然后返回
     l2.next = mergeTwoLists(l2.next, l1);
     return l2;
 }

}
```
4. 143.【重排链表】
  
  解题思路：
  
  思路1：
  
  明显可以看到，题目中有链表的反向遍历，但是单链表结构不支持随机遍历，因此，我们可以用一个线性表将该链表的所有节点存储，然后用双指针法解决问题：
```
 public void reorderList(ListNode head) {

 if (head == null) return;

 // 用一个线性表存储链表的所有节点   
 List<ListNode> list = new ArrayList<>();
 ListNode temp = head;
 while (temp != null) {
     list.add(temp);
     temp = temp.next;
 }

 // 重排
 int i = 0, j = list.size() - 1;
 while (i < j) {
     list.get(i).next = list.get(j);
     i++;
     if (i == j) break;
     list.get(j).next = list.get(i);
     j--;
 }
 // 最后，需要设置null
 list.get(i).next = null;

}
```
  思路2：
  
  首先，题目要求重排后的链表的形式，明显是：当前链表的前半，合并后半的逆序。
  
  因此，我们可以先找到链表中点，然后逆序遍历，最后合并。
5. 25.【k个一组翻转链表】
  
  解题思路：
  
  链表具有递归性质，而递归实际上就是分解问题，因此我们将该问题分解成一个个小问题来看。
  
  首先，从表头翻转第一个k的链表，翻转完毕后，剩下的不就是新的长度变短的链表吗？至此，递归的思路就出来了。
  
  如何翻转[a, a + k)的链表呢？我们之前翻转过整个链表，整个链表的翻转不就是[0, n)的翻转吗？因此套用思路即可。
  
  整体代码如下：
```
 public ListNode reverseKGroup(ListNode head, int k) {

 if (head == null) return null;

 // 先记录下剩下的链表表头
 ListNode a, b;
 a = b = head;
 for (int i = 0; i < k; i++) {
     // 说明剩下的链表个数不足k个，不用反转了，返回head即可
     if (b == null) return head;
     b = b.next;
 }

 // 利用迭代的方法翻转[a, b)的链表。
 ListNode pre = null, curr = a, next = a;
 while (curr != b) {
     next = curr.next; 

     curr.next = pre;

     pre = curr;
     curr = next;
 }

 // 递归
 a.next = reverseKGroup(b, k);

 return pre;
}
```
6. 61.【旋转链表】
  
  解题思路：
  
  先连成环，然后在需要的位置断开即可。
7. 445.【两数相加II】
  
  解题思路：
  
  通过栈这种数据结构来完成。

2021/06/18 今日算法 （复习开始）

知识点

LeetCode算法题

2021/06/18 今日算法（复习开始）