Leetcode - 链表篇

移除链表元素

203

• 设定虚拟头节点 ListNode dummy = new ListNode(-1,head);

• 一个指向前节点，一个指向当前节点

  • 当前节点的值 = val时，跳过当前节点

    if (cur.val == val){
        pre.next = cur.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 {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
​
        //因为删除可能涉及到头节点，所以设置dummy节点，统一操作
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null){
            if (cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O（n）

• 空间复杂度：O（1）

设计链表

707

//单链表
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 MyLinkedList {
​
    // 存储链表元素的个数
    int size;
    // 虚拟头节点
    ListNode dummy;
​
    // 初始化链表
    public MyLinkedList() {
        size = 0;
        dummy = new ListNode(-1);
    }
    
    // 获取第index个节点的数值
    public int get(int index) {
        //若index非法，返回-1
        if (index < 0 || index >= size) return -1;
​
        ListNode cur = dummy;
        for (int i = 0;i < index + 1;i++){//包含一个虚拟头节点，故查找第index+1个节点
            cur = cur.next;
        }
        return cur.val;
    }
    
    //在链表最前面插入一个节点
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点
    // 若index等于链表长度，则说明新插入的节点为链表的尾节点
    // 若index大于链表的长度，则返回为空
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
​
        size++;
        ListNode pre = dummy;
        for (int i = 0;i < index;i++){//找到要插入节点的前驱
            pre = pre.next;
        }
​
        ListNode toAdd = new ListNode(val);
        toAdd.next = pre.next;
        pre.next = toAdd;
    }
    
    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
​
        size--;
        ListNode cur = dummy;
        for (int i = 0;i < index;i++){//找到要删除节点的前驱
            cur = cur.next;
        }
​
        cur.next = cur.next.next;
    }
}

//双链表
class ListNode{
    int val;
    ListNode next,prev;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
}
​
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头节点
    ListNode dummy_head;
    //虚拟尾节点
    ListNode dummy_tail;
​
    //初始化链表
    public MyLinkedList() {
        size = 0;
        dummy_head = new ListNode(-1);
        dummy_tail = new ListNode(-1);
        dummy_head.next = dummy_tail;
        dummy_tail.prev = dummy_head;
    }
    //获取第index个节点的数值
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0|| index >= size){
            return -1;
        }
        ListNode cur = dummy_head;
        for (int i = 0;i < index + 1;i++){//包含一个虚拟头节点，故查找第index+1个节点
            cur = cur.next;
        }
        return cur.val;
    }
    //在链表最前面插入一个节点
    public void addAtHead(int val) {
        ListNode cur = dummy_head;
        ListNode new_Node = new ListNode(val);
        new_Node.next = cur.next;
        cur.next.prev = new_Node;
        cur.next = new_Node;
        new_Node.prev = cur;
        size++;
    }
    //在链表最后插入一个节点
    public void addAtTail(int val) {
        ListNode cur = dummy_tail;
        ListNode new_Node = new ListNode(val);
        new_Node.next = dummy_tail;
        new_Node.prev = cur.prev;
        cur.prev.next = new_Node;
        cur.prev = new_Node;
        size++;
​
    }
    
    //在第 index 个节点之前插入一个新节点，例如idnex为0，那么新插入的节点为链表的新头节点
    //若 index 等于链表的长度，则说明新插入的节点为链表的尾节点
    //若 index 大于链表的长度，则返回为空
    public void addAtIndex(int index, int val) {
        if (index > size){
            return;
        }
        if (index < 0){
            index = 0;
        }
        //找到要插入节点的前驱
        ListNode cur = dummy_head;
        for (int i = 0;i < index;i++){
            cur = cur.next;
        }
        ListNode new_Node = new ListNode(val);
        new_Node.next = cur.next;
        cur.next.prev = new_Node;
        new_Node.prev = cur;
        cur.next = new_Node;
        size++;
    }
    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size){
            return;
        }
        //找到要删除节点的前驱
        ListNode cur = dummy_head;
        for (int i = 0;i < index;i++){
            cur = cur.next;
        }
        cur.next.next.prev = cur;
        cur.next = cur.next.next;
        size--;
    }
}

反转链表

206. 反转链表 - 力扣（Leetcode）

双指针

• 设立两个指针：pre、cur

• 将pre -> cur 转为 pre <- cur

  temp = cur.next; // 保存下一个节点
  cur.next = pre;

• 再更新pre、cur

  pre = cur;
  cur = temp;

/**
 * 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 pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null){
            temp = cur.next; // 保存下一个节点
            cur.next = pre;
            
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

递归

//递归
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
​
    ListNode reverse(ListNode pre,ListNode cur){
        if (cur == null) return pre;
​
        ListNode temp = cur.next; // 先保存下一个节点
        cur.next = pre;
​
        //更新pre、cur位置
        // pre = cur、cur = temp
        return reverse(cur,temp);
    }
}
​
//从后向前递归
class Solution {
    public ListNode reverseList(ListNode head) {
        //边缘条件判断
        if (head == null) return null;
        if (head.next == null) return head;
​
        //递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        head.next.next = head;//翻转头节点与第二个节点的指向
        head.next = null;//此时的head节点为尾节点，next需指向NULL
        return last;
    }
}

反转链表Ⅱ

92. 反转链表 II - 力扣（Leetcode）

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置虚拟头节点
        ListNode dummy = new ListNode(-1,head);
​
        ListNode pre = dummy;
        for (int i = 0;i < left - 1;i++){//找到left节点的前一个节点
            pre = pre.next;
        }
​
        // pre再走right - left + 1步到right节点
        ListNode rightNode = pre;
        for (int i = 0;i < right - left + 1;i++){
            rightNode = rightNode.next;
        }
​
        // 找到left节点、right节点后一个节点
        ListNode leftNode = pre.next;
        ListNode succ = rightNode.next;
​
        // 切断连接
        pre.next = null;
        rightNode.next = null;
​
        //反转链表
        reverse(null,leftNode);
​
        // 拼接回原来的链表
        pre.next = rightNode;
        leftNode.next = succ;
        return dummy.next;
    }
​
    ListNode reverse(ListNode pre,ListNode cur){
        if (cur == null) return pre;
​
        ListNode temp = cur.next; // 先保存下一个节点
        cur.next = pre;
​
        //更新pre、cur位置
        // pre = cur、cur = temp
        return reverse(cur,temp);
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置虚拟头节点
        ListNode dummy = new ListNode(-1,head);
​
        ListNode pre = dummy;
        for (int i = 0;i < left - 1;i++){//找到left节点前的一个节点
            pre = pre.next;
        }
​
        ListNode cur = pre.next;
        ListNode next;
​
        for (int i = 0;i < right - left;i++){
            next = cur.next;
​
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
​
        }
​
        return dummy.next;
    }
}

两两交换链表中的节点

24

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
​
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null && cur.next != null){
            ListNode temp1 = cur.next;
            ListNode temp2 = cur.next.next;
​
            pre.next = temp1;
            cur.next = temp2;
            temp1.next = cur;
​
            pre = cur;
            cur = temp2;
        }
        return dummy.next;
    }
}

//递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = head.next;//获取当前节点的下一个节点
        ListNode new_Node = swapPairs(next.next);//进行递归
​
        //这里进行交换
        next.next = head;
        head.next = new_Node;
​
        return next;
    }
}

删除链表的倒数第N个节点

19

• 设立快慢指针fast、slow

• fast先走n步。当fast为null时，slow到达倒数第n个节点

• 记住 slow 节点前继，删除即跳过

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1,head);
​
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (n-- > 0){//使得fast与slow相差n步
            fast = fast.next;
        }
​
        //记住待删除节点slow的上一节点
        ListNode pre = null;
        while (fast != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre.next = slow.next; //绕过待删除节点
​
        return dummy.next;
    }
}

链表相交

面试题02.07

• 使两个链表在相同位置开始遍历

  1. 计算链表A、链表B的长度

  2. 使A的链表长度大于链表B的长度（不符合则交换链表A、B）

  3. 链表A先走 lenA-lenB的距离

  4. 遍历链表A、B，碰到相同值则相交直接返回

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
​
        int lenA = 0,lenB = 0;
        while (curA != null){//求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null){//求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
​
        //让curA成为最长链表的头，lenA为其长度
        if (lenB > lenA){
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
​
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //求长度差
        int gap = lenA - lenB;
        //让curA、curB位于同一起点
        while (gap-- > 0){
            curA = curA.next;
        }
        //遍历curA、curB,遇到相同则直接返回
        while (curB != null){
            if (curA == curB) return curA;
​
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

环形链表

141. 环形链表 - 力扣（Leetcode）

• 设立快慢指针fast、slow。fast每次走两步、slow每次走一步

• 若有环，fast和slow迟早相遇，即返回true。

• 若无环，则遍历到null时，返回为false

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

环形链表Ⅱ

142

相遇时

• slow走过：x + y

• fast走过：x + y + n(y + z)，n 为fast指针在环内走了n圈才遇到slow指针，y + z 为一圈内节点的个数

• fast = 2 * slow -> x + y + n(y + z) = 2(x + y)

• 化简得：x = (n - 1)(y +z) + z，意味着相遇节点、头节点同时出发，每次只走一步。相遇时即是环形入口的节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
​
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
​
            if (slow == fast){//有环
                ListNode index1 = fast; // 相遇节点
                ListNode index2 = head; // 头节点
                //两个指针，从头节点、相遇节点各走一步，直到相遇，相遇即为环入口
                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

两数相加

2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
​
        while (l1 != null || l2 != null){
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;//将两个链表的值，进行相加，并加上进位数
​
            carry = sum / 10;//计算进位数
            sum = sum % 10;//计算两个数的和，
​
            cur.next = new ListNode(sum);
            cur = cur.next;
​
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        //如果最后两个数，相加的时候有进位数的时候，就将进位数，赋予链表的新节点
        //两数相加最多小于20，所以值最大只能是1
        if (carry == 1){
            cur.next = new ListNode(carry);
        }
​
        //返回链表的头节点
        return pre.next;
    }
}

合并两个有序链表

21. 合并两个有序链表 - 力扣（Leetcode）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
​
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                cur.next = list1;
​
                cur = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
​
                cur = list2;
                list2 = list2.next;
            }
        }
        // 合并后,最多还有1个list不为空
        cur.next = list1 != null ? list1 : list2;
​
        return dummy.next;
    }
}

合并K个升序链表

23. 合并K个升序链表 - 力扣（Leetcode）

顺序合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0;i < lists.length;i++){
            ans = mergeTwoLists(ans,lists[i]);
        }
        return ans;
    }
​
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
​
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                cur.next = list1;
​
                cur = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
​
                cur = list2;
                list2 = list2.next;
            }
        }
        // 合并后,最多还有1个list不为空
        cur.next = list1 != null ? list1 : list2;
​
        return dummy.next;
    }
}

归并合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);
    }
​
    public ListNode merge(ListNode[] lists,int left,int right){
        if (left == right) return lists[left];
        if (left > right) return null;
​
        int mid = (left + right) >> 1;
​
        return mergeTwoLists(merge(lists,left,mid),merge(lists,mid + 1,right));
    }
​
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
​
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                cur.next = list1;
​
                cur = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
​
                cur = list2;
                list2 = list2.next;
            }
        }
        // 合并后,最多还有1个list不为空
        cur.next = list1 != null ? list1 : list2;
​
        return dummy.next;
    }
}

排序链表

归并排序

• subLength指定每次合并的子链表长度，1 -> 2 -> 4 -> ...

• 两两合并。确定两个链表头的节点，并与其他节点断开

  ListNode head1 = curr;// 第一个链表头
  for (int i = 1;i < subLength & curr.next != null;i++){
      curr = curr.next;
  }
  ​
  ListNode head2 = curr.next; // 第二个链表头，即链表1尾部的下一个位置
  curr.next = null; // 断开第一、第二个链表的连接
  curr = head2; // 将第二个链表头赋给curr
  for (int i = 1;i < subLength && curr != null && curr.next != null;i++){
      curr = curr.next;
  }
  ​
  ListNode next = null;//记录两个链表后的结束位置
  if (curr != null){
      next = curr.next;
      curr.next = null; // 拆开两个链表和剩余部分的连接
  }

• 合并这两个节点，并重新选取两个链表节点进行合并

  ListNode merged = mergeTwoLists(head1,head2);// 合并两个subLen长度的有序链表
  pre.next = merged;// pre.next指向排好序链表的头
  while (pre.next != null){// 将pre移动到subLen*2的位置去
      pre = pre.next;
  }
  curr = next; // 将curr重新标为剩下链表的开始位置

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null) return head;
​
        // 获取链表长度
        int n = 0;
        ListNode node = head;
        while (node != null){
            n++;
            node = node.next;
        }
​
        ListNode dummy = new ListNode(-1,head);
        for (int subLength = 1;subLength < n;subLength *= 2){
            ListNode pre = dummy;
            ListNode curr = dummy.next; // curr用于记录拆分链表的位置
​
            while (curr != null){// 如果链表没有被拆完
                ListNode head1 = curr;// 第一个链表头
                for (int i = 1;i < subLength & curr.next != null;i++){
                    curr = curr.next;
                }
​
                ListNode head2 = curr.next; // 第二个链表头，即链表1尾部的下一个位置
                curr.next = null; // 断开第一、第二个链表的连接
                curr = head2; // 将第二个链表头赋给curr
                for (int i = 1;i < subLength && curr != null && curr.next != null;i++){
                    curr = curr.next;
                }
​
                ListNode next = null;//记录两个链表后的结束位置
                if (curr != null){
                    next = curr.next;
                    curr.next = null; // 拆开两个链表和剩余部分的连接
                }
​
                ListNode merged = mergeTwoLists(head1,head2);// 合并两个subLen长度的有序链表
                pre.next = merged;// pre.next指向排好序链表的头
                while (pre.next != null){// 将pre移动到subLen*2的位置去
                    pre = pre.next;
                }
                curr = next; // 将curr重新标为剩下链表的开始位置
            }
        }
        return dummy.next;
    }
​
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
​
        ListNode dummy = new ListNode(-1);
​
        ListNode pre = dummy;
​
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                pre.next = list1;
                list1 = list1.next;
            } else{
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
​
        // 合并l1和l2后，最多只有一个还未被合并完
        pre.next = list1 == null ? list2 : list1;
        return dummy.next;
    }
}

对链表进行插入排序

147. 对链表进行插入排序 - 力扣（Leetcode）

插入排序

• 设立排好序的最后一个节点lastSorted，待插入的节点curr

• 当待插入的节点值大于最后一个节点时，不用处理。

  lastSorted = lastSorted.next;

• 当待插入的节点值小于最后一个节点时，需要将其放入排好序的正确位置

  lastSorted.next = curr.next; // 指向下一个待插入的节点
  ​
  ListNode pre = dummy;
  while (pre.next.val <= curr.val){//找到cur应该插入的位置
      pre = pre.next;
  }
  curr.next = pre.next;
  pre.next = curr;

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;
​
        ListNode dummy = new ListNode(-1,head);
​
        ListNode lastSorted = head;// 链表已经排好序的最后一个节点
        ListNode curr = lastSorted.next;// 待插入的元素并初始化
        while (curr != null){
            if (lastSorted.val <= curr.val){
                lastSorted = lastSorted.next;
            } else{
                lastSorted.next = curr.next;
​
                ListNode pre = dummy;
                while (pre.next.val <= curr.val){//找到cur应该插入的位置
                    pre = pre.next;
                }
                curr.next = pre.next;
                pre.next = curr;
            }
            curr = lastSorted.next; // 此时curr为下一个待插入的元素
        }
​
        return dummy.next;
    }
}