1、必会操作.md

### 反转链表

* 时间复杂度 O(n) ，定义三个指针

  ```java
  ListNode pre = null , cur = head , after = null;
  
  while(...){
      after = cur.next;
      cur.next = pre;
      pre = cur;
      cur = after;
      ...
  }
  ```





#### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)

难度简单1480收藏分享切换为英文接收动态反馈

反转一个单链表。

**示例:**

```
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
```



**题解**

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null, after = null;

        while(cur != null){
            after = cur.next;
            cur.next = pre;
            pre = cur;
            cur = after;
        }

        return pre;
    }
}
```



#### [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)

难度中等661收藏分享切换为英文接收动态反馈

反转从位置 *m* 到 *n* 的链表。请使用一趟扫描完成反转。

**说明:**
1 ≤ *m* ≤ *n* ≤ 链表长度。

**示例:**

```
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
```



**题解**

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        int idx =  1;
        ListNode pre = null;
        ListNode cur = head;
        ListNode after = cur.next;

        while(idx < m){
            pre = cur;
            cur = cur.next;
            idx ++;
        }

        ListNode target1 = pre;
        ListNode target2 = cur;

        while(idx <= n){
            after = cur.next;
            cur.next = pre;
            pre = cur;
            cur = after;
            idx ++;
        }

        if(target1 == null){
            head = pre;
        }else {
            target1.next = pre;
        }
        target2.next = cur;

        
        return head;
    }
}
```

### 基操

* 对于多数链表题来说，直接再开辟一个链表空间最简单
* 注意：凡是要把一个节点移动到其他位置，一定要改该节点前面的 next （所以说如果有要移动的情况，那么一定是前后指针遍历）
* 注意：如果把某个节点移到尾节点了，那么一定改该节点 next 为 null。



#### [86. 分隔链表](https://leetcode-cn.com/problems/partition-list/)

难度中等358收藏分享切换为英文接收动态反馈

给你一个链表和一个特定值 `x` ，请你对链表进行分隔，使得所有小于 `x` 的节点都出现在大于或等于 `x` 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

 

**示例：**

```
输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5
```



**示例**

```java
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallerListHead  = null;
        ListNode smallerListTail = null;

        ListNode BiggerListHead = null;
        ListNode BiggerListTail = null;

        ListNode node = head;
        while(node != null){
            if(node.val < x){
                if(smallerListHead == null){
                    smallerListHead = new ListNode(node.val);
                    smallerListTail = smallerListHead;
                }else {
                    smallerListTail.next = new ListNode(node.val);
                    smallerListTail = smallerListTail.next;
                }
            }else {
                if(BiggerListHead == null){
                    BiggerListHead = new ListNode(node.val);
                    BiggerListTail = BiggerListHead;
                }else {
                    BiggerListTail.next = new ListNode(node.val);
                    BiggerListTail = BiggerListTail.next;
                }
            }
            
            node = node.next;
        }

        ListNode res;
        if(smallerListHead != null){
            smallerListTail.next = BiggerListHead;
            res = smallerListHead;
        }else if(BiggerListHead != null){
            res = BiggerListHead;
        }else{
            res = null;
        }
        return res;
    }
}
```



#### [328. 奇偶链表](https://leetcode-cn.com/problems/odd-even-linked-list/)

难度中等375收藏分享切换为英文接收动态反馈

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

**示例 1:**

```
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
```

**示例 2:**

```
输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL
```



**题解**

```java
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }

        int sum = 1;
        ListNode tail = head;
        while(tail.next != null){
            tail = tail.next;
            sum ++;
        }

        int idx = 1;
        ListNode node = head;
        ListNode pre = null;

        while(idx <= sum){
            if(idx % 2 == 0){
                tail.next = node;
                tail = node;

                pre.next = node = node.next;
            }else {
                pre = node;
                node = node.next;
            }

            idx ++;
        }

        tail.next = null;
        return head;
    }
}
```



#### [2. 两数相加](https://leetcode-cn.com/problems/add-two-numbers/)

难度中等5583收藏分享切换为英文接收动态反馈

给你两个 **非空** 的链表，表示两个非负的整数。它们每位数字都是按照 **逆序** 的方式存储的，并且每个节点只能存储 **一位** 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 

**示例 1：**

![](https://img-blog.csdnimg.cn/20210210224745425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)


```
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
```

**示例 2：**

```
输入：l1 = [0], l2 = [0]
输出：[0]
```

**示例 3：**

```
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
```



**题解**

```java
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l1Node = l1;
        ListNode l2Node = l2;
        ListNode resHead = null;
        ListNode resTail = null;

        boolean flag = false;
        while(l1Node != null && l2Node != null){
            int data = l1Node.val + l2Node.val + (flag ? 1: 0);
            //=============完全相同的部分，但实在不好抽离================
            flag = false;
            if(data >= 10){
                data -= 10;
                flag = true;
            }
            
            if(resHead == null){
                resHead = resTail = new ListNode(data);
            }else {
                resTail.next = new ListNode(data);
                resTail = resTail.next;
            }
            //===========================================================

            l1Node = l1Node.next;
            l2Node = l2Node.next;
        }

        ListNode other = l1Node != null ? l1Node : l2Node;
        while(other != null){
            int data = other.val + (flag ? 1 : 0);
            //=============完全相同的部分，但实在不好抽离================
            flag = false;
            if(data >= 10){
                data -= 10;
                flag = true;
            }

            if(resHead == null){
                resHead = resTail = new ListNode(data);
            }else {
                resTail.next = new ListNode(data);
                resTail = resTail.next;
            }
            //===========================================================
            other = other.next;
        }

        if(flag){
            resTail.next = new ListNode(1);
        }

        return resHead;
    }
}
```



#### [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

**示例 1:**

```
输入: 1->1->2
输出: 1->2
```

**示例 2:**

```
输入: 1->1->2->3->3
输出: 1->2->3
```



**题解**

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return head;
        }
        
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null){
            if(pre.val == cur.val){
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }

        return head;
    }
}
```





#### [237. 删除链表中的节点](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/)

难度简单833收藏分享切换为英文接收动态反馈

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 **要被删除的节点** 。

 

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210210224813544.png)


 

**示例 1：**

```
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
```

**示例 2：**

```
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
```

 

**提示：**

- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。



**题解**

```java
class Solution {
    public void deleteNode(ListNode node) {
        ListNode preI = node;
        ListNode i = node.next;
        while(i != null){
            preI.val = i.val;
            if(i.next == null){
                break;
            }else{
                preI = i;
                i = i.next;
            }
        }

        preI.next = null;
    }
}
```