搞定大厂算法面试之leetcode精讲15.链表

2021-12-02 07:21:14 浏览数 (2)

搞定大厂算法面试之leetcode精讲15.链表

视频讲解（高效学习）:点击学习
目录：

1.开篇介绍

2.时间空间复杂度

3.动态规划

4.贪心

5.二分查找

6.深度优先&广度优先

7.双指针

8.滑动窗口

9.位运算

10.递归&分治

11剪枝&回溯

12.堆

13.单调栈

14.排序算法

15.链表

16.set&map

17.栈

18.队列

19.数组

20.字符串

21.树

22.字典树

23.并查集

24.其他类型题

链表操作如下图：

动画过大，点击查看

时间复杂度：
  • prepend: O(1)
  • append: 如果已知尾节点O(1)，否则需要遍历到尾节点，然后加入新节点O(n)
  • insert: 插入到已知节点的后面O(1)，需要先查找后插入O(n)
  • lookup: O(n)
  • Delete：删除已知节点O(1)，需要先查找后删除O(n)
206. 反转链表（easy）
方法1.头插法：

动画过大，点击查看

  • 思路：准备一个临时节点，然后遍历链表，准备两个指针head和next，每次循环到一个节点的时候，将head.next指向temp.next，并且将temp.next指向head，head和next向后移一位。
  • 复杂度分析：时间复杂度：O(n)， n为链表节点数，空间复杂度：O(1)
js:
代码语言：javascript复制
var reverseList = function (head) {
  let temp = new ListNode();
  let next = null;
  while (head) {
    next = head.next;//下一个节点
    head.next = temp.next;
    temp.next = head;//head接在temp的后面
    head = next;//head向后移动一位
  }
  return temp.next;
};
方法2.迭代法：

动画过大，点击查看

  • 思路: 遍历链表，准备prev，curr，next三个指针，在遍历的过程中，让当前指针curr.next指向前一个指针prev，然后不断让prev，curr，next向后移动，直到curr为null
  • 复杂度分析：时间复杂度：O(n)， n为链表节点数，空间复杂度：O(1)
js：
代码语言：javascript复制
var reverseList = function (head) {
  let prev = null;
  let curr = head;
  let next = null;
  while (curr !== null) {
    next = curr.next;//next向后移动一位
    curr.next = prev;//让当前指针curr.next指向前一个指针prev
    prev = curr;//prev向后移动一位
    curr = next;//curr向后移动一位
    //[curr.next, prev, curr] = [prev, curr, curr.next]
  }
  return prev;
};
java：
代码语言：javascript复制
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
方法3.递归：

动画过大，点击查看

  • 思路：用递归函数不断传入head.next，直到head==null或者heade.next==null，到了递归最后一层的时候，让后面一个节点指向前一个节点，然后让前一个节点的next置为空，直到到达第一层，就是链表的第一个节点，每一层都返回最后一个节点。
  • 复杂度分析：时间复杂度：O(n)，n是链表的长度。空间复杂度：O(n)， n是递归的深度，递归占用栈空间，可能会达到n层
js:
代码语言：javascript复制
var reverseList = function(head) {
    if (head == null || head.next == null) {//递归终止条件
        return head;
    }
    const newHead = reverseList(head.next);//递归调用reverseList
    head.next.next = head;//到了递归最后一层的时候，让后面一个节点指向前一个节点
    head.next = null;//前一个节点的next置为空
    return newHead;//返回最后一个节点
};
Java:
代码语言：javascript复制
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
92. 反转链表 II(medium)
方法1

动画过大，点击查看

  • 思路：切断left到right的子链，然后反转，最后在反向连接
  • 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

代码语言：javascript复制
var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;//虚拟头节点

    let pre = dummyNode;
    for (let i = 0; i < left - 1; i  ) {//pre遍历到left的前一个节点
        pre = pre.next;
    }

    let rightNode = pre;
    for (let i = 0; i < right - left   1; i  ) {//rightNode遍历到right的位置
        rightNode = rightNode.next;
    }

    let leftNode = pre.next;//保存leftNode
    let curr = rightNode.next;//保存rightNode.next

   //切断left到right的子链
    pre.next = null;
    rightNode.next = null;

  //206题的逻辑 反转left到right的子链
    reverseLinkedList(leftNode);

    //返乡连接
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};

const reverseLinkedList = (head) => {
    let pre = null;
    let cur = head;

    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

java：

代码语言：javascript复制
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode
        for (int i = 0; i < left - 1; i  ) {
            pre = pre.next;
        }

        ListNode rightNode = pre;
        for (int i = 0; i < right - left   1; i  ) {
            rightNode = rightNode.next;
        }

        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        pre.next = null;
        rightNode.next = null;

        reverseLinkedList(leftNode);

        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

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

动画过大，点击查看

  • 思路：从left遍历到right，在遍历的过程中反转链表
  • 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

代码语言：javascript复制
var reverseBetween = function(head, left, right) {
    const dummy_node = new ListNode(-1);
    dummy_node.next = head;//虚拟头节点
    let pre = dummy_node;
    for (let i = 0; i < left - 1;   i) {//pre前进到left的前一个节点
        pre = pre.next;
    }

    let cur = pre.next;
    for (let i = 0; i < right - left;   i) {//循环right - left次 反转中间的节点
        const next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy_node.next;//返回虚拟头节点的next
};

java：

代码语言：javascript复制
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i  ) {
            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 dummyNode.next;
    }
}
24. 两两交换链表中的节点 （medium）
方法1.递归：

ds_17

  • 思路：用递归函数不断传入链表的下一个节点，终止条件是head === null|| head.next === null，也就是至少存在两个节点进行两两交换，在最后一层的时候开始两两反转，让当前递归层的head.next指向交换后返回的头节点，然后让反转后的新的头节点指向当前层的head的节点，这样就实现了两两交换，最后返回反转后链表的头节点
  • 复杂的分析：时间复杂度O(n)， n 是链表的节点数量。空间复杂度O(n)，n是递归调用的栈空间

js:

代码语言：javascript复制
var swapPairs = function(head) {
    if (head === null|| head.next === null) {//终止条件，必须要有两个节点
        return head;
    }
    const newHead = head.next;//反转后链表的头节点，
    head.next = swapPairs(newHead.next);//让当前递归层的head.next指向交换后返回的头节点
    newHead.next = head;//让反转后的新的头节点指向当前层的head的节点
    return newHead;//返回反转后的头节点
};

Java:

代码语言：javascript复制
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
方法2.循环(虚拟头节点)

ds_18

  • 思路：设置虚拟头节点dummyHead，让dummyHead.next指向head,当temp.next !== null && temp.next.next !== null的时候，也就是dummyHead后面存在至少两个节点，才开始两两交换节点。交换之前准备三个指针temp指向dummyHead，node1是dummyHead后面的第一个节点，node2是dummyHead后的第二个节点，交换的时候让temp.next指向node2，node1.next指向node2.next，node2.next指向node1，每次循环迭代让这三个节点后移一个节点，最后返回dummyHead.next，核心步骤是 temp.next = node2; node1.next = node2.next; node2.next = node1;
  • 复杂的分析：时间复杂度O(n)， n 是链表的节点数量。空间复杂度O(1)，

Js:

代码语言：javascript复制
var swapPairs = function(head) {
    const dummyHead = new ListNode(0);//虚拟头节点
    dummyHead.next = head;//初始的时候让虚拟头节点指向head，
    let temp = dummyHead;//temp指针
    while (temp.next !== null && temp.next.next !== null) {//循环条件，dummyHead后存在至少两个节点
        const node1 = temp.next;//node1指针，即dummyHead后的第一个节点
        const node2 = temp.next.next;//node2指针，即dummyHead后的第二个节点
        temp.next = node2;//下面三行是两两交换的核心代码
        node1.next = node2.next;
        node2.next = node1;
        temp = node1;//后移一个节点的位置
    }
    return dummyHead.next;//返回交换后的头节点
};

Java:

代码语言：javascript复制
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}
146. LRU 缓存机制 （medium）

ds_19

ds_212

  • 思路：准备一个哈希表和双向链表存储键值对，哈希表O(1)就能查找到键值对，双向链表方便从链表头部新增节点，也可以从队尾删除节点
    1. get的时候，查找哈希表中有没有该键值对，不存在就返回-1，存在就返回该节点的值，并且将该节点移动到链表的头部
    2. put的时候，查找哈希表中有没有该键值对，如果存在就更新该节点，并且移动到链表的头部，不存在就创建一个节点，加入到哈希表和链表的头部，并且让节点数count 1，如果超出容量，就从队尾删除一个节点
  • 复杂度：put、get时间复杂度都是O(1)，空间复杂度O(c)，c是LRU的容量

js:

代码语言：javascript复制
class ListNode {
    constructor(key, value) {//双向链表的单个节点
        this.key = key
        this.value = value
        this.next = null //指向后一个节点
        this.prev = null //指向前一个节点
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity //容量
        this.hashTable = {} //存放键值对信息
        this.count = 0 //键值对数量
        this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入
        this.dummyTail = new ListNode() //dummy尾节点 方便在链表从末尾删除
        this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接
        this.dummyTail.prev = this.dummyHead
    }

    get(key) {
        let node = this.hashTable[key]//查找哈希表中的键值对
        if (node == null) return -1 //不存在该键值对 返回-1
        this.moveToHead(node) //移动到链表头
        return node.value
    }

    put(key, value) {
        let node = this.hashTable[key] //哈希表中查找该键值对
        if (node == null) {
            let newNode = new ListNode(key, value) //不存在就创建节点
            this.hashTable[key] = newNode //加入哈希表
            this.addToHead(newNode) //加入链表头
            this.count   //节点数 1
            if (this.count > this.capacity) { //超过容量 从队尾删除一个
                this.removeLRUItem()
            }
        } else {
            node.value = value //键值对存在于哈希表中 就更新
            this.moveToHead(node) //移动到队头
        }
    }

    moveToHead(node) {
        this.removeFromList(node)//从链表中删除节点
        this.addToHead(node)//将该节点添加到链表头
    }

    removeFromList(node) {//删除的指针操作
        let tempForPrev = node.prev
        let tempForNext = node.next
        tempForPrev.next = tempForNext
        tempForNext.prev = tempForPrev
    }

    addToHead(node) {//加入链表头的指针操作
        node.prev = this.dummyHead
        node.next = this.dummyHead.next
        this.dummyHead.next.prev = node
        this.dummyHead.next = node
    }

    removeLRUItem() {
        let tail = this.popTail()//从链表中删除
        delete this.hashTable[tail.key]//从哈希表中删除
        this.count--
    }

    popTail() {
        let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除
        this.removeFromList(tailItem)
        return tailItem
    }
}

Java:

代码语言：javascript复制
public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }

        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {

            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
              size;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
237. 删除链表中的节点（easy）

ds_125

  • 思路：将要删除节点的下一个节点的值覆盖自己的值，然后让当前节点指向下一个节点的next
  • 复杂度：时间复杂度和空间复杂度都是O(1)

js：

代码语言：javascript复制
var deleteNode = function(node) {
    node.val = node.next.val//将要删除节点的下一个节点的值覆盖自己的值Ï
    node.next = node.next.next//让当前节点指向下一个节点的next
};

java；

代码语言：javascript复制
public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}
19. 删除链表的倒数第 N 个结点 (medium)
方法1：栈
  • 思路：循环链表，将所有的节点入栈，然后在弹出栈n次，就是我们需要删除的节点
  • 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(L)。
方法2:遍历2次
  • 思路：遍历一次链表的到链表的长度L，在重头遍历到L-n 1的位置就是需要删除的节点。
  • 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(1)
方法3:遍历1次

动画过大，点击查看

  • 思路：新建dummy节点指向head，指针n1，n2指向head，循环n2指针到n的位置，然后在同时移动n1，n2，直到结尾，n1，n2的距离是n，此时n1的位置就是需要删除元素的位置
  • 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(1)

js:

代码语言：javascript复制
var removeNthFromEnd = function (head, n) {
    let dummy = new ListNode();
    dummy.next = head;
    let n1 = dummy;
    let n2 = dummy;
    for (let i = 0; i <= n; i  ) {//n2移动n 1次
        n2 = n2.next;
    }
    while (n2 !== null) {//同时移动n1，n2
        n1 = n1.next;
        n2 = n2.next;
    }
    n1.next = n1.next.next;//删除元素
    return dummy.next;
};

java:

代码语言：javascript复制
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode n1 = dummy;
        ListNode n2 = dummy;
        for (int i = 0; i <= n; i  ) {//n2移动n次
            n2 = n2.next;
        }
        while (n2 != null) {//同时移动n1，n2
            n1 = n1.next;
            n2 = n2.next;
        }
        n1.next = n1.next.next;//删除元素
        return dummy.next;
    }
}
203. 移除链表元素 (easy)
方法1.递归
  • 思路：递归调用函数removeElements，传入head.next和 val，如果当前元素值是val，则返回下一个元素，否则直接返回当前元素
  • 复杂度：时间复杂度O(n)，n是链表的长度，空间复杂度是O(n)，递归栈的深度，最大为n

js：

代码语言：javascript复制
//例：0->1->2->3  val=2
//level1: 0.next = removeElements(1, 2);   return 1     0->1->3->null
//level2: 1.next = removeElements(2, 2);   return 3     1->3->null
//level3: 2.next = removeElements(3, 2);   return 3     2->3->null
//level4: 3.next = removeElements(null, 2);  return null;     3->null

var removeElements = function(head, val) {
    if (head === null) {//递归终止 遍历完了链表
      return head;
    }
    head.next = removeElements(head.next, val);//递归调用函数removeElements
    return head.val === val ? head.next : head;//如果当前元素值是val，则返回下一个元素，否则直接返回当前元素
};

java：

代码语言：javascript复制
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}
方法2.迭代
  • 思路：创建dummy节点，将dummy节点的next指向head，temp指向dummy，当temp的next不为null 不断移动temp指针，当temp的next值是要删除的 则删除该节点
  • 复杂度：时间复杂度O(n)，n是链表的长度，空间复杂度是O(1)

js：

代码语言：javascript复制
//2->1->2->3
//dummy->2->1->2->3
var removeElements = function(head, val) {
    const dummyHead = new ListNode(0);//创建dummy节点，将dummy节点的next指向head，temp指向dummy
    dummyHead.next = head;
    let temp = dummyHead;
    while (temp.next !== null) {//当temp的next不为null 不断循环节点
        if (temp.next.val == val) {
            temp.next = temp.next.next;//当temp的next值是要删除的 则删除该节点
        } else {
            temp = temp.next;//移动temp指针
        }
    }
    return dummyHead.next;
};

java：

代码语言：javascript复制
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}
2. 两数相加 （medium）

ds_166

  • 思路：循环两个链表，计算每个节点相加的和在加进位，然后计算进位，处理最后一次的进位。
  • 复杂度：时间复杂度O(max(m，n))，循环的次数是链表较长的那个。空间复杂度O(1)

js：

代码语言：javascript复制
var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {//循环l1,l2链表
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1   n2   carry;//两链表节点相加在加进位
        if (!head) {
            head = tail = new ListNode(sum % 10);//当没有节点的时候新建节点
        } else {
            tail.next = new ListNode(sum % 10);//有节点的时候则加入tail节点的后面
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);//求进位
        if (l1) {//移动l1指针
            l1 = l1.next;
        }
        if (l2) {//移动l2指针
            l2 = l2.next;
        }
    }
    if (carry > 0) {//最后一位节点是否有进位
        tail.next = new ListNode(carry);
    }
    return head;
};

java：

代码语言：javascript复制
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1   n2   carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}
21. 合并两个有序链表 (easy)
方法1.递归

ds_167

  • 思路：递归合并节点，当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并，直到两个链表有一个的nxet不存在了，那就没法分割问题了，只能返回
  • 复杂度：时间复杂度O(m n)，m、n为两个链表的长度，每次递归排除掉一个节点，总递归次数是m n。空间复杂度O(m n)，递归栈空间

js：

代码语言：javascript复制
var mergeTwoLists = function(l1, l2) {
  //递归终止 分隔到不能分割 也就是两个链表有一个的nxet不存在了 那就没法分割问题了 只能返回
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {//当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并
        l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子问题
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

java：

代码语言：javascript复制
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
方法2.迭代

动画过大，点击查看

  • 思路：设立虚拟头节点prehead，prev节点初始指向prehead，循环两个链表，两个链表中小的节点接在prev的后面，不断移动prev，最后返回prehead.next
  • 复杂度：时间复杂度O(m n)，m、n为两个链表的长度，循环m n次。空间复杂度O(1)

js：

代码语言：javascript复制
var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);//虚拟头节点

    let prev = prehead;
    while (l1 != null && l2 != null) {//循环两个链表
        if (l1.val <= l2.val) {//小的节点接在prev的后面
            prev.next = l1;
            l1 = l1.next;//向后移动l1
        } else {
            prev.next = l2;//向后移动l2
            l2 = l2.next;
        }
        prev = prev.next;////向后移动prev
    }

    prev.next = l1 === null ? l2 : l1;//两个链表一个遍历完，另一个可能还没遍历完，没遍历完的接上

    return prehead.next;//返回prehead.next
};

java：

代码语言：javascript复制
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}
83. 删除排序链表中的重复元素 (easy)

时间复杂度：O(n)。空间复杂度O(1)

js:

代码语言：javascript复制
var deleteDuplicates = function(head) {
    let cur = head;
    while(cur && cur.next) {
        if(cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
};

java:

代码语言：javascript复制
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}
328. 奇偶链表 (medium)

动画过大，点击查看

  • 思路：奇偶指针循环链表，奇数指针不断串连奇数节点，偶数指针不断串连偶数节点，最后奇数指针的结尾连接偶数节点的开始
  • 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

代码语言：javascript复制
var oddEvenList = function(head) {
    if (head === null) {
        return head;
    }
    let evenHead = head.next;
    let odd = head, even = evenHead;
    while (even !== null && even.next !== null) {//偶数指针不为空 继续循环
        odd.next = even.next;//奇数指针指向偶数指针的next
        odd = odd.next;//移动奇数指针
        even.next = odd.next;//偶数指针指向奇数指针的next
        even = even.next;//移动偶数指针
    }
    odd.next = evenHead;//奇数指针结尾连接上偶数指针的开始
    return head;
};

java：

代码语言：javascript复制
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
腾讯广告算法大赛

0 人点赞