搞定大厂算法面试之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.nextnode2.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;
    }
}
最新:
react源码解析
搞定大厂算法面试之leetcode精讲
vue3.0源码解析(筹划中)

潇晨简介:前阿里、道富前端工程师,撸过码、创过业,热于技术分享,很高兴认识你
愿景:做一个程序员高效深度学习社区
请尊重劳动果实 否则追究法律责任

公众号
管理员wx