# 链表

核心

操作 next 指针；
注意保留 pre 指针，防止链表断了找不回来了；
虚拟头结点是一个好东西，可以兼容多种情况；
快慢指针可以用来寻找链表中点；

# 反转链表

# Leetcode 206 Reverse Linked List

https://leetcode-cn.com/problems/reverse-linked-list/

思路一：迭代

反转链表的核心就是把每一个指针反向，也就是 cur.next = cur.pre，所以：

记录 cur 指针；
用 pre 记录 cur 的前一个结点，默认为 null；
记录下 next 指针，防止反转 cur 指针后丢了链表后面的部分；
循环操作：cur.next =cur.pre，pre = cur，cur = next 直到遍历完链表，满足 cur = null；
最后返回 pre，即为反转后的链表。

/**
 * 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) {
    
        if(head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode pre = null;

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

思路二：递归

递归的思路，其实就是将 while 循环换成递归，主要是确定递归出口和递归体。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    return help(nil, head)
}

func help(pre *ListNode, cur *ListNode) *ListNode {
    // 递归出口
    if cur == nil {
        return pre
    }

    // 反转
    next := cur.Next
    cur.Next = pre

    // 继续往后
    return help(cur, next)

}

# Leetcode 92 Reverse Linked List II

https://leetcode-cn.com/problems/reverse-linked-list-ii/

只反转链表中的一个部分，这个时候可以考虑建立一个虚拟头结点，最后返回 dummyHead.next 即可。这样做的好处是可以兼容两种情况：

反转起始点在头结点
反转起始点不在头结点

中间反转的过程跟反转整个链表一样，只不过我们需要考虑的条件就只是 i 和 left 以及 right 的大小关系而已。思路如下：

建立 dummyHead；
让 i 走到 left 的部分，此时 dummyHead -> ..... -> leftPre -> cur( i / left ) -> ..... -> null，leftPre 的存在是为了避免丢掉 left 之前的链表；
反转 left 到 right 之间的链表，到最后 cur 指向的是 right 后面的链表。这个时候我们用 rightPre 来指向反转后的尾结点，这样它可以快速指向 right 之后部分的链表，即反转后：dummyHead ..... -> leftPre -> left[反转]right(rightPre) -> cur(i) ->....-> null；
返回 dummyHead.next 即可。

/**
 * 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 {
    // left 和 right 都是从 1 开始
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if ( head == null || head.next == null){
            return head;
        }

        // 使用一个虚拟头结点，兼容从开头反转和非开头反转两种情况
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        ListNode cur = head;
        ListNode leftPre = dummyHead;

        // 找到 left
        // 题目保证了 left 和 right 是合法的
        // 所以无需考虑空指针异常
        int i = 1;
        while(i < left){
            leftPre = cur;
            cur = cur.next;
            i++;
        }

        // 跳出 while 循环的时候， i = left
        // dummyHead -> ..... -> leftPre -> cur -> ..... -> null
        //                                   i
        //                                  left

        ListNode pre = null;

        // 开始节点反转后就是 right 所在位置的结点
        ListNode rightPre = cur;

        // 开始反转
        while(i <= right) {
            i++;

            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 跳出 while 循环的时候， i = right + 1
        // dummyHead ..... -> leftPre -> left[反转]right -> cur->....-> null
        //                                        rightPre   i

        leftPre.next = pre;
        rightPre.next = cur;

        return dummyHead.next;
    }
}

# Leetcode 24 Swap Nodes In Pairs

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

本题我们仔细分析后就会发现，其实就是比较复杂的链表变换，关键点就在于指针的操作，要避免链表没有指针指着而导致链表丢失。

具体操作如下所示：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    // 虚拟头结点
    dummyHead := &ListNode{Next: head}
    pre := dummyHead
    cur := head

    // 两两交换
  	// cur  即图中的 node1
    // next 即图中的 node2
    for cur != nil && cur.Next != nil {
        next := cur.Next
        // ① 
        pre.Next = next
        // ② 
        cur.Next = next.Next
        // ③ 
        next.Next = cur
        // 交换下一对
        pre = cur
        cur = cur.Next
    }
    return dummyHead.Next
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
			
      	// 虚拟头结点，这样就不用考虑头两个结点交换后新的头结点的确定了
        ListNode dummyHead = new ListNode(0, head);
        ListNode cur = head;
        ListNode pre = dummyHead;
				
      	// 有两个才交换，单个不用交换
        while(cur != null && cur.next != null){
            ListNode next = cur.next;
            ListNode newCur = next.next;
            // 交换 cur 和 next
            pre.next = next;
            next.next = cur;
            cur.next = newCur;
            pre = cur;
            cur = newCur;
        }

        return dummyHead.next;
    }
}

# Leetcode 25 Reverse Nodes In K Group

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

每 k 个进行翻转，最重要的就是要确保翻转的时候不要丢了头尾，在保证了这一点后，本题其实就是简单的链表翻转的一个升级而已。具体思路如下：

每次翻转确定前一个节点 left 和起始节点 start；
判断是否有 k 个节点，没有则直接返回（本题要求）；
从 start 开始翻转 k 个节点，返回下一个 start；
以此循环；

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {

    dummyHead := &ListNode{Next: head}
    left := dummyHead
    start := head

    for  {
        // 不足 k 个，直接返回
        if !checkK(start, k) {
            break
        }
        // 有 k 个翻转
        left = reverse(left, start, k)

        if left == nil || left.Next == nil {
            break
        }
        // 确定下一个起点
        start = left.Next

    }
    return dummyHead.Next
}

// 从 head 开始翻转 k 个
// left 用来连接前面的
// 返回下一个翻转起点的前一个节点（即新的 left
func reverse(left *ListNode, head *ListNode, k int) *ListNode {

    cur := head
    i := 1
    var pre *ListNode

    // 翻转
    for cur != nil && i <= k {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
        i++
    }

    //连接
    left.Next = pre
    head.Next = cur

    return head
}

// 检查是否有 k 个元素
func checkK(head *ListNode, k int) bool {
    cur := head
    i := 0
    for cur != nil && i < k {
        cur = cur.Next
        i++
    }
    return i >= k
}

# 虚拟头结点

# Leetcode 203 Remove Linked List Elements

https://leetcode-cn.com/problems/remove-linked-list-elements/

因为要移除的节点有可能是头结点，所以我们可以设置一个虚拟头结点来兼容这种情况，最后直接返回 dummyHead.next 即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
				
      	// 虚拟头结点
        ListNode dummyHead = new ListNode(0, head);
        ListNode pre = dummyHead;
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            if(cur.val != val){
                pre = cur;
                cur = next;
            } else {
              	// 移除节点
                pre.next = next;
              	// 释放节点，减少内存消耗
              	cur.next = null;
                cur = next;
            }
        }

        return dummyHead.next;
    }
}

# Leetcode 82 Remove Duplicates From Sorted List II

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

因为题目要求只要那个节点重复了，就要删得一个都不剩，所以在第一步去重后，我们还需要加一个 flag 来标记当前这个节点是否是重复的，是否需要删除。具体思路如下：

建立虚拟头节点 dummyHead，兼容头结点需要删除的情况；
建立一个标记 repeat，来记录在去重后是否需要删除 cur 节点；
判断 cur 和 next 是否相等：
1. 不等，判断 cur 之前是否是重复节点：
  1. 不是，后移；
  2. 是，删除 cur；
2. 相等，删除 cur
最后再检查是否需要删除最后一个节点；

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
				
      	// 虚拟头结点，兼容需要删除头结点这种情况
        ListNode dummyHead = new ListNode(0, head);
        ListNode pre = dummyHead;
        ListNode cur = head;

        // 记录是否重复过
        boolean repeat = false;

        while(cur != null && cur.next != null){
            ListNode next = cur.next;
          	// cur 和 next
            if(cur.val != next.val){
                // 如果之前是重复的，那就要删除掉 cur
              	// 此时 pre 不用变
                if(repeat){
                    repeat = false;
                    pre.next = next;
                    cur.next = null;
                    cur = next;
                }else{
                  	// 不重复，则直接往后滑，此时要更新 pre
                    pre = cur;
                    cur = next;
                }
            } else {
                // cur 和 next 重复，删除掉 cur
              	// 此时 pre 不用变
                repeat = true;
                pre.next = next;
                cur.next = null;
                cur = next;
            }
        }

        // 如果最后一个重复，则删除掉最后一个，也就是 cur
        if(repeat){
            pre.next = null;
        }

        return dummyHead.next;
    }
}

# Leetcode 21 Merge Two Sorted Lists

https://leetcode-cn.com/problems/merge-two-sorted-lists/

合并两个有序链表，因为我们不知道哪个链表的头结点更小，所以无法确定 result 的头结点，这个时候虚拟头结点就会很有用了。不管是 l1 和 l2 先大，都能兼容。具体思路如下：

建立一个虚拟头结点 dummyHead；
依次扫描 l1 和 l2，谁小谁先入 result；
最后看看谁还没扫描完，直接接在 result 后面即可。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        // 建立一个虚拟头结点，不管 l1 和 l2 谁先大都兼容
        ListNode dummyhead = new ListNode();
        ListNode cur = dummyhead;
        
        while(l1 != null && l2 != null){
          	// l1 小，l1 入
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            } else {
                // l2 小，l2 入
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        // 剩 l1，直接把 l1 接在后面
        if(l1 != null){
            cur.next = l1;
        }

        // 剩 l2，直接把 l2 接在后面
        if(l2 != null){
            cur.next = l2;
        }

        return dummyhead.next;
    }
}

# Leetcode 147 Insertion Sort List

https://leetcode.cn/problems/insertion-sort-list/

本题明确要求要插入排序。思路：

为了避免要插入到头部，需要频繁确定新的头结点，直接加入 dummyHead 一劳永逸；
新建一个有序链表，默认放入第一个元素 head；
用 cur 遍历 head 链表，不断找到 cur 的位置并插入；
中间要注意释放 cur 后面的指针，不然会 OOM；

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    // 有序链表
    dummyHead := &ListNode{Next: head}

    // 扫描先有链表
    cur := head.Next
    // 把 head 后面清空，不然 OOM
    head.Next = nil
    for cur != nil {
        // 在有序链表中找到 cur 的位置
        scan := dummyHead.Next
        scanPre := dummyHead

        // 尝试找第一个比 cur 大的
        for scan != nil {
            if scan.Val <= cur.Val {
                scanPre = scan
                scan = scan.Next
            } else {
                break
            }
        }
        if scan == nil {
            // 没有比 cur 大的，那就插在后面
            scanPre.Next = cur
            next := cur.Next
            // 释放 cur 后面的指针，不然 OOM
            cur.Next = nil
            cur = next
        } else {
            // 有比 cur 大的，那就插在 scanPre 和 scan 中间
            next := cur.Next
            scanPre.Next = cur
            cur.Next = scan
            cur = next
        } 
    }
    return dummyHead.Next
}

# 快慢指针

# Leetcode 148 Sort List

https://leetcode.cn/problems/sort-list/

本题要求时间复杂度为 n(logn)，空间复杂度为 O(1)，那就只能归并排序了。归并排序需要找中点，那就可以用上 快慢指针 了。思路如下：

不断使用快慢指针将链表进行二等分为 left 和 right；
再对 left 和 right 进行二等分；
等到 left 和 right 都只剩下 1 个元素的时候，就天然有序了，使用 mergeSortedList 进行合并；
将合并好后的链表再两两进行合并，即可。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func sortList(head *ListNode) *ListNode {

	// 递归出口
	if head == nil || head.Next == nil {
		return head
	}

  // 二分
	left, right := binayList(head)
  // 划分到只剩下一个的时候，就天然有序了
	if left.Next != nil {
    // 不止一个，那就需要递归排序
		left = sortList(left)
	}

	if right.Next != nil {
		right = sortList(right)
	}
	
  // 现在 left 和 right 都是有序的，合并即可
	return mergeSortedList(left, right)
}

// 快慢指针二分链表
func binayList(head *ListNode) (*ListNode, *ListNode) {

	if head == nil || head.Next == nil {
		return head, nil
	}

	p1 := head
	p2 := head.Next

	for p2 != nil && p2.Next != nil {
		p1 = p1.Next
		p2 = p2.Next.Next
	}

	after := p1.Next
	p1.Next = nil
	return head, after
}

// 合并有序链表
func mergeSortedList(l1 *ListNode, l2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	cur := dummyHead

	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			next := l1.Next
			cur.Next = l1
			l1 = next
		} else {
			next := l2.Next
			cur.Next = l2
			l2 = next
		}
		cur = cur.Next
	}

	if l1 != nil {
		cur.Next = l1
	}

	if l2 != nil {
		cur.Next = l2
	}

	return dummyHead.Next
}

# Leetcode 143 Reorder List

https://leetcode.cn/problems/reorder-list/

L0 → L1 → … → Ln - 1 → Ln - > L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

经观察，本题即把后面的一半进行旋转，然后跟前面的一半交替衔接在一起。具体思路如下：

快慢指针寻找中点；
将后半部分旋转；
两链表交替连接。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil {
        return
    }
    // 快慢指针寻找中点
    p1 := head
    p2 := head.Next
    for p2 != nil && p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next.Next
    }
    after := p1.Next
    p1.Next = nil

    // 反转 after
    after = reverseList(after)

    // 连接 head 和 after
    linkTwoList(head, after)
}

// 连接 l1 和 l2，l1 在前
// | len(l1) - len(l2)| <= 1
func linkTwoList(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    cur1 := l1
    cur2 := l2

    for cur1 != nil && cur2 != nil {
        next1 := cur1.Next
        next2 := cur2.Next

        cur1.Next = cur2

       // 因为 | len(l1) - len(l2)| <= 1
       // 所以可以直接退出
        if next1 == nil {
            break
        }
        cur1.Next.Next = next1
        cur1 = next1

        cur2 = next2

    }
    return l1
}


// 反转链表
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var pre *ListNode
    cur := head

    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre

}

# Leetcode 234 Palindrome Linked List

https://leetcode.cn/problems/palindrome-linked-list/

思路一：将整个链表反转，再一一比较；

思路二：快慢指针找到中点，反转后半部门，再一一比较；此时如果是奇数个节点的话，前半部分链表多出的一个，就不用比较了，因为必然相等。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {

    if head == nil || head.Next == nil {
        return true
    }

    // 快慢指针找到中点
    p1 := head
    p2 := head.Next

    for p2 != nil && p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next.Next
    }

    after := p1.Next
    p1.Next = nil
		
  	// 反转后半部分
    after = reverse(after)

    // len(后) <= len(前)，故只要短的重复了，那就回文了
    for after != nil {
        if head.Val != after.Val {
            return false
        }
        head = head.Next
        after = after.Next
    }
    return true
}


// 反转链表
func reverse(head *ListNode) *ListNode {

    if head == nil || head.Next == nil {
        return head
    }

    var pre *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

# 滑动窗口

# Leetcode 19 Remove Nth Node From End Of List

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

本题要我们删除倒数第 n 个结点，很明显，在保证 n <= size 的情况下（题目已保证），我们只需要建立一个长度固定为 n 的窗口，然后滑动到链表结束，删掉左窗口即可。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	
  	// 只要遇到删除，就需要 dummyHead 和 pre
  	dummyHead := &ListNode{Next: head}
    pre := dummyHead
    // 1. 建立长度为 n 的窗口
    left := head
    right := head
    for ; n > 1; n-- {
        right = right.Next
    }

    // 2. 滑动窗口到 right 到链表末尾
    for right.Next != nil {
        pre = pre.Next
        left = left.Next
        right = right.Next
    }

    // 3. 删除 left
    pre.Next = left.Next
    left.Next = nil
    left = nil

    return dummyHead.Next
}

# Leetcoce 61 Rotate List

https://leetcode.cn/problems/rotate-list/

整个链表向右旋转 k 个，其实就是将后面的补到前面，思路还是比较清晰的。具体如下：

遍历一遍链表，确定链表元素个数 i；
k = k % i，确定实际有意义的旋转位数，避免重复；
确定大小为 k 的窗口；
将窗口移动到链表末尾；
将尾部转移到前部，完成。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }
    // 先统计一遍链表个数，对 k 取模，避免重复劳动
    cur := head
    i := 0
    for cur != nil {
        i++
        cur = cur.Next
    }

    // 真实只需要移动 k % i 个位置
    k = k % i

    if k == 0 {
        return head
    }

    // 现在可以保证 k <= size
    // 所谓移动 k 个位置，就是将后 k 个元素，转移到前面

    // 1. 构建大小为 k 的窗口
    i = 1
    left := head
    right := head
    for i < k {
        right = right.Next
        i ++
    }

    pre := &ListNode{Next:left}
    // 2. 将大小为 k 的窗口移动到链表末尾，找到要旋转的部分
    for right.Next != nil {
        pre = pre.Next
        left = left.Next
        right = right.Next
    }

    // 3. 将 [left, right] 移动到前面
    pre.Next = nil
    right.Next = head
    return left

}

# 一分为二

# Leetcode 86 Partition List

https://leetcode-cn.com/problems/partition-list/

class Solution {
    public ListNode partition(ListNode head, int x) {

        if(head == null || head.next == null){
            return head;
        }
			
      	// 小于 x 的部分
        ListNode smallDummyHead = new ListNode();
        ListNode smallCur = smallDummyHead;
        
        // 大于 x 的部分
        ListNode bigDummyHead = new ListNode();
        ListNode bigCur = bigDummyHead;

        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            if(cur.val < x){
                smallCur.next = cur;
                smallCur = cur;
            } else {
                bigCur.next = cur;
                bigCur = cur;
            }
            // 避免链表循环
            cur.next = null;
            cur = next;
        }

        smallCur.next = bigDummyHead.next;
        return smallDummyHead.next;
    }
}

# Leetcode 328 Odd Even Linked List

https://leetcode-cn.com/problems/odd-even-linked-list/

简单的思路就是搞两个头，就是奇数头和偶数头，然后搞一个 index 来记录当前扫描到链表的位置，对 2 取模，然后加到对应的链表即可，扫描完再串起来。

class Solution {
    public ListNode oddEvenList(ListNode head) {

        if(head == null || head.next == null || head.next.next == null){
            return head;
        }

        // 奇头
        ListNode oddHead = head;
        ListNode oddCur = oddHead;
        // 偶头
        ListNode evenHead = head.next;
        ListNode evenCur = evenHead;
				
      	// 索引来记录要加在奇还是加在偶
        int curIndex = 3;
        ListNode cur = head.next.next;
        while(cur != null){
            ListNode next = cur.next;
            if(curIndex % 2 == 1){
                // 奇
                oddCur.next = cur;
                oddCur = cur;
            } else {
                // 偶
                evenCur.next = cur;
                evenCur = cur;
            }
            cur = next;
            curIndex++;
        }

        evenCur.next = null;
        oddCur.next = evenHead;
        return oddHead;
    }
}

# 合二为一

# Leetcode 2 Add Two Numbers

https://leetcode-cn.com/problems/add-two-numbers/

因为数字是逆序的，所以不需要反转链表，直接使用一个进位标志 flag 来标志是否需要进位，然后模仿真实场景下的算术手算即可。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode result = new ListNode(0);
        ListNode cur = result;

        // 进位标志
        boolean flag = false;
			
      	// 相加
        while(l1 != null && l2 != null){
            ListNode next = new ListNode();
            if(flag) {
                int sum = l1.val + l2.val + 1;
                if(sum >= 10){
                    next.val = sum - 10;
                    flag = true;
                }else {
                    next.val = sum;
                    flag = false;
                }
            } else {
                int sum = l1.val + l2.val;
                if(sum >= 10){
                    next.val = sum - 10;
                    flag = true;
                }else{
                    next.val = sum;
                    flag = false;
                }
            }
            cur.next = next;
            cur = next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        // 剩下 l1
        if(l2 == null){
            while(l1 != null){
                ListNode next = new ListNode();
                if(flag) {
                    int sum = l1.val + 1;
                    if(sum >= 10){
                        next.val = sum - 10;
                    }else {
                        next.val = sum;
                        flag = false;
                    }
                } else {
                    next.val = l1.val;
                }
                cur.next = next;
                cur = next;
                l1 = l1.next;
            }
        }
        
        // 剩下 l2
        if(l1 == null){
            while(l2 != null){
                ListNode next = new ListNode();
                if(flag) {
                    int sum = l2.val + 1;
                    if(sum >= 10){
                        next.val = sum - 10;
                    }else {
                        next.val = sum;
                        flag = false;
                    }
                } else {
                    next.val = l2.val;
                }
                cur.next = next;
                cur = next;
                l2 = l2.next;
            }
        }

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

        return result.next;
    }
}

# Leetcode 445 Add Two Numbers II

https://leetcode-cn.com/problems/add-two-numbers-ii/

此题跟 Leetcode 2 不同，数字是正序的，所以我们需要把 l1 和 l2 先反转后再相加，最后再把 result 反转回来，即可得到答案。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if(l1.val == 0){
            return l2;
        }

        if(l2.val == 0){
            return l1;
        }

        // 反转
        l1 = reserveLinkedList(l1);
        l2 = reserveLinkedList(l2);

        ListNode result = new ListNode(0);
        ListNode cur = result;

        // 进位标志
        boolean flag = false;

        while(l1 != null && l2 != null){
            ListNode next = new ListNode();
            if(flag) {
                int sum = l1.val + l2.val + 1;
                if(sum >= 10){
                    next.val = sum - 10;
                    flag = true;
                }else {
                    next.val = sum;
                    flag = false;
                }
            } else {
                int sum = l1.val + l2.val;
                if(sum >= 10){
                    next.val = sum - 10;
                    flag = true;
                }else{
                    next.val = sum;
                    flag = false;
                }
            }
            cur.next = next;
            cur = next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        // 剩下 l1
        if(l2 == null){
            while(l1 != null){
                ListNode next = new ListNode();
                if(flag) {
                    int sum = l1.val + 1;
                    if(sum >= 10){
                        next.val = sum - 10;
                    }else {
                        next.val = sum;
                        flag = false;
                    }
                } else {
                    next.val = l1.val;
                }
                cur.next = next;
                cur = next;
                l1 = l1.next;
            }
        }
        
        // 剩下 l2
        if(l1 == null){
            while(l2 != null){
                ListNode next = new ListNode();
                if(flag) {
                    int sum = l2.val + 1;
                    if(sum >= 10){
                        next.val = sum - 10;
                    }else {
                        next.val = sum;
                        flag = false;
                    }
                } else {
                    next.val = l2.val;
                }
                cur.next = next;
                cur = next;
                l2 = l2.next;
            }
        }

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

        // 转回来
        return reserveLinkedList(result.next);

    }


    // 反转链表
    public ListNode reserveLinkedList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head;
        ListNode pre = null;

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

        return pre;
    }
}

# 经典问题

# Leetcode 83 Remove Duplicateds from Sorted List

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

因为链表是天然有序的，所以很明显就只有两种情况：

cur.val != next.val 无需删除，cur 往后移；
cur.val == next.val，需要删除 next，直接 cur.next = next.next；

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

        ListNode cur = head;

        while(cur != null && cur.next != null){
            ListNode next = cur.next;
            if(cur.val != next.val){
                cur = next;
            } else {
                cur.next = next.next;
                next.next = null;
                next = null;
            }
        }

        return head;
    }
}

← 查找表栈丨队列 →