链表medium专题

总结

1. yes代表独立做出来,no代表没有独立做出来(no越多代表越没有思路)，需要看一下解法
2. 递归，链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
3. 链表的关键就是断链和重链，无论是递归还是非递归，都需要在合适的地方断链和重链
4. 对于链表问题，如果需要对头节点可能发生变更，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点 head。

LeetCode2 合并两个有序链表 (yes)

（1）题目：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

（2）思路：

• 处理不同的长度的链表

• 处理十进制导致链表长度+1的情况

  • 一种结果链表长度为二者最长长度
  • 一种结果链表长度为二者最长长度+1

• 利用本身函数递归来计算1，999这种极端情况

（3）代码：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    ListNode head = new ListNode();
    ListNode index = head;
    int tenCount = 0;

    while (l1 != null && l2 != null) {
        index.next = new ListNode(countSingle(l1.val + l2.val + tenCount));
        tenCount = l1.val + l2.val + tenCount > 9 ? 1 : 0;
        index = index.next;
        l1 = l1.next;
        l2 = l2.next;
    }

    if (tenCount > 0) {
      	// 利用本身函数递归来计算1，999这种极端情况
        index.next = addTwoNumbers(new ListNode(tenCount), l1 != null ? l1 : l2);
    } else {
        index.next = l1 != null ? l1 : l2;
    }

    return head.next;
}

private int countSingle(int value) {
    return value > 9 ? value - 10 : value;
}

LeetCode24 两两交换链表中的节点 (yes)

（1）题目：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4] 输出：[2,1,4,3]

（2）思路：

• 最开始想用非递归，用循环遍历的方式去解，声明P,Q两个节点，循环交换，但是发现后面链接的时候需要先交换在链接，而不能先链接在交换，这就无法使用循环，转而使用递归
• 递归和循环在链表中不能同时出现

（3）代码：

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

    ListNode nHead = new ListNode();
    nHead.next = head.next;
    ListNode p = head, q = head.next;
    p.next = swapPairs(q.next);
    q.next = p;

    return nHead.next;
}

LeetCode61 旋转链表 (yes)

（1）题目：

你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

输入：head = [0,1,2], k = 4 输出：[2,0,1]

输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]

（2）思路：

• 先计算链表长度n，并对k取余，计算出真正的k
• 在倒数K的位置截断链表，这里用到了双指针(倒数k的方式，先走k，然后再走到末尾间距K，从而使倒数)
• 还有一种思路代替双指针，首位相接，变成环然后在从首部进行遍历

（3）代码：

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || k == 0) {
        return head;
    }

    int count = 0;
    ListNode index = head;
    while (index != null) {
        index = index.next;
        count++;
    }

    int real = k % count;
    if (count - real == 0) {
        return head;
    }

    index = head;
    while (real != 0) {
        index = index.next;
        real--;
    }
    ListNode temp = head;
    while (index.next != null) {
        index = index.next;
        temp = temp.next;
    }

    index.next = head;
    ListNode nHead = temp.next;
    temp.next = null;

    return nHead;
}

LeetCode82 旋转链表2 (no)

（1）题目：

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]

输入：head = [1,1,1,2,3] 输出：[2,3]

（2）思路：

• 不同于83旋转链表对于重复的节点只保留一个，本题需要把所有重复的节点都要删除
• 引入pre前置节点，当head删除时能够更优雅的处理
• 需要在遍历的过程中再次引入循环来处理多个重复节点的问题

（3）代码：

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

    ListNode pre = new ListNode();
    pre.next = head;
    ListNode p = pre;

    while (head != null && head.next != null) {
        if (head.val != head.next.val) {
            head = head.next;
            p = p.next;
        } else {
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            if (head == null) {
                p.next = head;
            } else {
                p.next = head.next;
                head = head.next;
            }
        }
    }

    return pre.next;
}

LeetCode86 分隔链表 (no)

（1）题目：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]

（2）思路：

• pre:哑节点
• p:遇到小于x的最后一个
• q:遇到大于等于x的第一个
• 遍历过程，从大于开始，遇到小于的则把这个节点追加到小于的链表下。整个过程是不断链的
• 还有一种解法就是断链，分别持有一个大于链表和一个小于链表，遍历过程中根据条件分别在尾部进行追加，最后把两个链表合并

（3）代码：

public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pre = new ListNode();
    pre.next = head;
    ListNode p = pre;
    ListNode q, temp, qq;
    while (p.next != null && p.next.val < x) {
        p = p.next;
    }
    q = p.next;
    if (q != null) {
        ListNode index = q;
        qq = index;
        while (index != null) {
            if (index.val < x) {
                temp = index.next;
                p.next = index;
                index.next = q;
                p = index;
                index = temp;
                if (qq != null) {
                    qq.next = index;
                }
            } else {
                qq = index;
                index = index.next;
            }
        }
    }

    return pre.next;
}

LeetCode143 重排链表 (no)

（1）题目：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]

（2）思路：

• 思路一：

  • 把链表转成数组，然后操作下标处理数组，最后把处理好的数组转成链表

• 思路二：

  • 获取中间节点，使用快慢指针
  • 把中间节点进行逆转，从而后半段链接是逆序
  • 前半段和后半段进行遍历链接

（3）代码：

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) {
        return;
    }

    ListNode middleNode = middleNode(head);
    ListNode reverse = reverse(middleNode.next);
    middleNode.next = null;

    ListNode index = head, temp, temp1;
    while (reverse != null) {
        temp = index.next;
        temp1 = reverse.next;
        index.next = reverse;
        reverse.next = temp;
        reverse = temp1;
        index = temp;
    }
}

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

    ListNode p = head, q = head;
    while (q.next != null && q.next.next != null) {
        p = p.next;
        q = q.next.next;
    }

    return p;
}

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

    ListNode reverse = reverse(head.next);
    head.next.next = head;
    head.next = null;

    return reverse;
}

LeetCode147 排序链表 (no)

（1）题目：

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

输入：head = [4,2,1,3] 输出：[1,2,3,4]

（2）思路：

• 链表的插入排序: 插入时不需要移动链表元素，但是需要遍历到插入的位置，需要从头向后遍历
• 数组的插入排序: 需要移动数组元素，是从后向前遍历

（3）代码：

/**
 * 链表的插入排序
 * 插入时不需要移动链表元素，但是需要遍历到插入的位置，需要从头向后遍历
 */
public ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode pre = new ListNode(head.val - 1);
    pre.next = head;
    ListNode lastSort = head, cur = head.next, index, temp, temp1;
    while (cur != null) {
        if (cur.val >= lastSort.val) {
            // 有序，无序插入
            lastSort = cur;
            cur = cur.next;
        } else {
            // 从头遍历进行插入
            index = pre;
            temp1 = cur.next;
            while (index != null) {
                if (index.next.val > cur.val) {
                    temp = index.next;
                    index.next = cur;
                    cur.next = temp;
                    lastSort.next = temp1;
                    break;
                } else {
                    index = index.next;
                }
            }
            cur = temp1;
        }

    }

    return pre.next;
}

/**
 * 数组的插入排序
 * 需要移动数组元素，是从后向前遍历
 */
public void insertSort(int[] nums) {
    if (null == nums || nums.length == 1) {
        return;
    }

    int temp = 0, i, j;
    for (i = 1; i < nums.length; i++) {
        temp = nums[i];
        // 从尾部遍历进行移动元素并插入
        for (j = i - 1; j >= 0 && nums[i] < nums[j]; j--) {
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = temp;
    }
}

LeetCode148 排序链表 (nono)

（1）题目：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入：head = [4,2,1,3] 输出：[1,2,3,4]

（2）思路：

• 获取链表中间节点，使用快慢指针
• 递归对子链表排序
• 合并两个有序链表leetcode21

（3）代码：

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

    ListNode mid = middleNode(head);
    ListNode middle = mid.next;
    mid.next = null;

    ListNode left = sortList(head);
    ListNode right = sortList(middle);

    return merge(left, right);
}

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

    ListNode p = head, q = head;
    while (q.next != null && q.next.next != null) {
        p = p.next;
        q = q.next.next;
    }

    return p;
}

private ListNode merge(ListNode h1, ListNode h2) {
    if (h1 == null) {
        return h2;
    }
    if (h2 == null) {
        return h1;
    }

    ListNode head = new ListNode();
    ListNode index = head;
    while (h1 != null && h2 != null) {
        if (h1.val < h2.val) {
            index.next = h1;
            h1 = h1.next;
        } else {
            index.next = h2;
            h2 = h2.next;
        }
        index = index.next;
    }
    if (h1 == null) {
        index.next = h2;
    }
    if (h2 == null) {
        index.next = h1;
    }

    return head.next;
}

LeetCode237 删除链表中的节点 (nono)

（1）题目：

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

输入：head = [4,5,1,9], node = 5 输出：[4,1,9]

（2）思路：

• 不删node，而是删node的下一个节点，不过是把value给更换，因为值唯一，所以看起来是删除掉node

（3）代码：

public void deleteNode(ListNode node) {
    if (node == null) {
        return;
    }

    int temp = node.next.val;
    node.next = node.next.next;
    node.val = temp;
}