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

原创

全栈潇晨

发布于 2021-12-02 07:21:14

3820

发布于 2021-12-02 07:21:14

文章被收录于专栏：高级前端工程师学习必备高级前端工程师学习必备

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

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

链表操作如下图：

动画过大，点击查看

时间复杂度：

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:

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：

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：

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:

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:

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：

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：

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：

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：

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:

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:

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:

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:

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:

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:

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：

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

java；

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:

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:

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：

//例：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：

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：

//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：

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：

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：

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：

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：

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：

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：

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:

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:

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：

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：

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;
    }
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛

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

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

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

目录：

链表操作如下图：

时间复杂度：

206. 反转链表（easy）

方法1.头插法：

js:

方法2.迭代法：

js：

java：

方法3.递归：

js:

Java:

92. 反转链表 II(medium)

方法1

方法2

24. 两两交换链表中的节点 （medium）

方法1.递归：

方法2.循环(虚拟头节点)

146. LRU 缓存机制 （medium）

237. 删除链表中的节点（easy）

19. 删除链表的倒数第 N 个结点 (medium)

方法1：栈

方法2:遍历2次

方法3:遍历1次

203. 移除链表元素 (easy)

方法1.递归

方法2.迭代

2. 两数相加 （medium）

21. 合并两个有序链表 (easy)

方法1.递归

方法2.迭代

83. 删除排序链表中的重复元素 (easy)

328. 奇偶链表 (medium)

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

24. 两两交换链表中的节点（medium）

146. LRU 缓存机制（medium）

2. 两数相加（medium）