LeetCode刷题—链表

发表于 分类于

LeetCode刷题

数据结构：

一、链表

160，相交链表，easy

206，反转链表，easy

21，合并两个有序链表，easy

83，删除排序链表中的重复元素，easy

83-Ⅱ.删除排序链表中的重复元素，middle

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

24，两两交换链表中的节点，middle

445，两数相加Ⅱ，middle

234，回文链表，easy

725，分隔链表，middle

328，奇偶链表，middle

160，相交链表，easy

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

image-20201116222545595

image-20201116222612234

image-20201116222642573

  • 方法：双指针。
    • 思路：定义节点pA指向headA，节点pB指向headB。
      • 如果两链表长度相同
        • 有交点，返回此交点
        • 没有交点，返回null
      • 如果两链表长度不同，先走完的指针指向另一个链表的头节点（如示例2的pB先走完，则指向headA），两指针再次出发，直到后走完的指针也走完了当前链表，使其指向另一链表（即pA走完，指向headB），两指针再次出发，直到找到交点或没有交点走完两链表。
    • 代码：
/**
 * 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) {
        //双指针，pA与pB如果能相遇，说明两个链表长度相同且有交点；第一遍不能相遇，pA转移到pB,pB转移到pA
        //再次遍历，如果能相遇说明有交点

        ListNode pA = headA;
        ListNode pB = headB;
//判别两个链表是否为空
        if (pA == null || pB == null) {
            return null;
        }
//长度不同会有先走完链表的
        while(pA != null && pB != null){
            pA = pA.next;
            pB = pB.next;
        }
//A先走完,转向headB pB同理
        if(pA == null){
            pA = headB;
        }
        else {
            pB = headA;
        }
//再次同时走，A继续向前，B转为headA        
        while(pA != null && pB != null){
            pA = pA.next;
            pB = pB.next;
        }
        if(pA == null){
            pA = headB;
        }
        else {
            pB = headA;
        }
//pA在B链表，pB在A链表，同时向前找交点
        while(pA != pB){
            pA = pA.next;
            pB = pB.next;
        }
        return pA;
    }
}

简化：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA == null ? headB:pA.next;
            pB = pB == null ? headA:pB.next;
        }
        return pA;
    }
}
  • 注意点：边界条件的判断：两链表可能为空。

206，反转链表，easy

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

  • 方法一：递归。

    • 思路：先递归到底, 找到最后一个节点, 然后从最后一个节点开始, 把箭头方向掉转。

    image-20201203164846365

    • 递归出口：链表为空或递归到链表的尾节点

      image-20201203164821559

    • 递归体：假如归到节点2，

      image-20201203164342559
      image-20201203164342559

    • 代码：

class Solution {
    public ListNode reverseList(ListNode head) {
//方法一：递归
        //终止条件：链表为空或递归到链表的尾节点时
        if(head == null || head.next == null) return head;

        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return cur;
    }
}

  • 方法二：迭代。

    • 思路：构建新链表，将原链表加入新链表，并调转顺序。

    image-20201203165433510

    直到head = null

    • 代码：
class Solution {
    public ListNode reverseList(ListNode head) {
    	ListNode newHead = null; //null
        while(head != null){
            ListNode temp = head.next;//保存后面用的新链表 2—>3->4->null
            head.next = newHead;      //null<-1
            newHead = head;           //更新结果链表 1为newHead
            head = temp;              //更新原链表 2—>3->4->null中的2为head
        }
        return newHead;
    }
}

21，合并两个有序链表，easy

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
  • 方法一：迭代。
    • 思路：建立新节点（值为0），再定义一个临时节点temp存储链表。比较 l1.val 与 l2.val 。如果 l1.val < l2.val，temp的下个节点设为l1，并将l1 向右移；如果 l1.val >= l2.val，对 l2 进行上述操作。如果一个链表全部存完为空，将另一个链表剩余节点加入temp.next。最后返回newHead.next。
    • 代码：
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //方法一、迭代。新建链表
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode newHead = new ListNode(0);
        ListNode temp = newHead;
        //l1与l2都不为空，较小的加入新链表
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                temp.next = l1;
                l1 = l1.next;
            }
            else if(l1.val >= l2.val){
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
            if(l1 == null){
                temp.next = l2;
            }
            if(l2 == null){
                temp.next = l1;
            }
        }
        return newHead.next;
    }
}
  • 方法二：递归。思路和上面一致。
  • 代码：
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode newHead = new ListNode(0);
        if(l1.val < l2.val){
            newHead = l1;
            newHead.next = mergeTwoLists(l1.next,l2);
        }
        else if(l1.val >= l2.val){
            newHead = l2;
            newHead.next = mergeTwoLists(l1,l2.next);
        }
        return newHead;
    }
}

83，删除排序链表中的重复元素，easy

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3
  • 方法一：直接法。
    • 思路：定义辅助单指针temp = head，比较temp与temp.next的值，如果相同，temp.next = temp.next.next，即image-20201205102048317

​ 如果不同，temp = temp.next，指针右移。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
     	ListNode temp = head;
        while(temp != null && temp.next != null){
            if(temp.val == temp.next.val){
                temp.next = temp.next.next;
            }
            else{
                temp = temp.next;
            }
        }
        return head;
    }
}
  • 方法二：双指针。
    • 思路：快慢指针。快指针用于探路，慢指针为结果链表指针。快指针如果与慢指针的值相等，快指针右移；不相等，保存到慢指针快指针再右移。
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode right = head.next;
        ListNode left = head;
        while(right != null){
            if(right.val != left.val){
                left.next = right;
                left = left.next;
            }
            else{
                right = right.next;
            }
        }
        //断开与后面重复元素的连接
        left.next = null;
        return head;
    }
}
  • 方法三：递归。
    • 思路：把链表看成 头节点->没有重复元素的排序链表，则比较头节点与子链表的头节点，如果相同，返回子链表的头节点；否则，返回head。
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
//递归出口 空链表和链表只有头节点
        if(head == null || head.next == null) return head;

        ListNode newHead = deleteDuplicates(head.next);
        head.next = newHead;

        return head.val == newHead.val ? newHead : head;
    }
}

83-Ⅱ.删除排序链表中的重复元素，middle

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3
  • 方法一：递归。
    • 思路：和上面那道题思路类似，但要判断头节点与后面元素是否相同。如果相同，找到第一个不重复的元素开始递归；如果不同，与上面题类似。
    • 代码：
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
//递归
        if(head == null || head.next == null) return head;
        //如果head与后面的节点重复，找到第一个不重复的节点，进行递归。
        if(head.val == head.next.val){
            while(head != null && head.next != null && head.val == head.next.val){
                head = head.next;
            }
            return deleteDuplicates(head.next);
        }
        else{
            ListNode newHead = deleteDuplicates(head.next);
            head.next = newHead;

            return head;
        }
    }
}
  • 方法二：双指针-快慢指针。
    • 思路：建立虚拟头节点dummy，双指针left指向dummy，right指向head，判断left.next 与 right.val是否相等。如果不相等，两指针右移；如果相等，right需要跳过所有重复数字，再令left的下一位为 right.next（第一个不重复的数字）。最后返回dummy之后的节点。
    • 代码：
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
//双指针，建立虚拟头节点
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode left = dummy;
        ListNode right = head;
        while(right != null && right.next != null){
            if(left.next.val != right.next.val){
                left = left.next;
                right = right.next;
            }
            else{
                while(right != null && right.next != null && left.next.val == right.next.val){
                    right = right.next;//right右移直到right.next不是重复数字
                }
                left.next = right.next;//left下一位是去掉重复数字之后的数字
                right = right.next;//继续右移
            }
        }
        return dummy.next;
    }
}

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
  • 方法一：先求出链表长度，就可以找到要删除节点的前一个节点，再使他指向后一个节点即可。
    • 代码：
class Solution {
//先得到长度，再单指针跳过倒数第n个元素 
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || head.next == null) return null;
        ListNode temp = head;

        int length = getLength(head);
        if(length == n) return head.next;

        for(int i = 0; i < length - n - 1; i++){
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return head;
    }
    public int getLength(ListNode head){
        int length = 1;
        while(head.next != null){
            length++;
            head = head.next;
        }
        return length;
    }
}
  • 方法二：双指针-快慢指针。
    • 思路：令快指针先走 n 步，慢指针再与快指针同时出发，直到快指针走到链表尾部，此时慢指针走到要删除节点的前一个节点，跳过即可。有些类似第160题.相交链表
    • 代码：
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;
        //快指针先走n步
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        //如果此时fast为空，说明删除的是头节点
        if(fast == null){
            return head.next;
        }
        //fast走到头，此时slow走到要删除节点的前一个
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

24，两两交换链表中的节点，middle

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

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

image-20201206195646801

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]
  • 方法一：递归。
    • 思路：两个相邻节点看为一组，组间节点交换（递归实现），再调整组间顺序。
    • 代码：
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        //两个相邻节点为一组，使后一个节点的指针指向前一个，组间指向也需要调整
        //先保存节点2
        ListNode temp = head.next;
        //头节点下一个节点为递归的结果（1->4->3）
        head.next = swapPairs(head.next.next);
        //2->1->4->3
        temp.next = head;

        return temp;
    }
}
  • 方法二：迭代。
    • 思路：定义一个虚拟头节点dummy，三个指针：left、right用于进行交换，temp用于连接两次迭代之间的节点。
    • 代码：
class Solution {
    public ListNode swapPairs(ListNode head) {
    //迭代
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode left = dummy;
        ListNode right = dummy; 
        ListNode temp = dummy;
        while(right != null && right.next != null && right.next.next != null){
            //分别向前走一步、两步
            left = left.next; // 1
            right = right.next.next; //2

            //使下次循环的1指向4
            temp.next = right;
            left.next = right.next;
            right.next = left;
            //2->1->3->4
        
            //再使temp、right都指向1.下次迭代时left为3，right为4
            temp = left;
            right = left;
        }
        return dummy.next;
    }
}

445，两数相加Ⅱ，middle

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 8 -> 0 -> 7
  • 题目说明：题目中说明最高位位于链表头部，即 7243 + 564 = 7807，最后输出的即7 -> 8 -> 0 -> 7。
  • 方法一：借助栈。
    • 思路：逆序先想到栈来存储链表节点的值，相加后再弹出，存储到一个新的链表。注意要记录进位，加到下一位。
    • 图解：image-20201207160650072
    • 代码：
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//法一：栈+取和的个位
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        
        int carry = 0;//相加的进位
        ListNode head = null;
        //有非空栈或carry > 0就进行相加操作
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){ 
            
            int sum = carry;//两数的和
            sum += stack1.isEmpty() ? 0 : stack1.pop();
            sum += stack2.isEmpty() ? 0 : stack2.pop();

            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;

            carry = sum / 10;
        }
        return head;
    }
}

注意：while条件里添加carry > 0是为了

输入:(5) + (5)
输出: 1->0

也可以单独判断carry，如果stack1、stack2都为空了但还有进位，则创建新节点加入结果。

while(!stack1.isEmpty() || !stack2.isEmpty() ){ 
            
            int sum = carry;//两数的和
            sum += stack1.isEmpty() ? 0 : stack1.pop();
            sum += stack2.isEmpty() ? 0 : stack2.pop();

            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;

            carry = sum / 10;
        }
        if(carry > 0){
            ListNode node1 = new ListNode(carry);
            node1.next = head;
            head = node1;
            }
        return head;
}
  • 方法二：反转链表。
    • 思路：因为要从链尾开始相加，所以先反转链表，两个链表从头开始相加节点的值，再将新的链表反转，得到结果。
    • 代码：
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //法二：反转链表 3->4->2->7 4->6->5  7 -> 0 -> 8 ->7反转输出结果
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode newl1 = reverse(l1);
        ListNode newl2 = reverse(l2);
       
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;//进位
        while(newl1 != null || newl2 != null || carry > 0){
            int sum = carry;
            sum += newl1 == null ? 0 : newl1.val;
            sum += newl2 == null ? 0 : newl2.val;

            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = node;

            carry = sum / 10;
            if(newl1 != null) newl1 = newl1.next;
            if(newl2 != null) newl2 = newl2.next;
        }
        ListNode res = reverse(dummy.next);
        return res;
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode node = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

  • 扩展：另一道类似题

    image-20200805204018584.png
    image-20200805204018584.png
    • 题目说明：逆序存储，即链尾为高位，相加得到结果仍要逆序输出。
    • 代码：
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1;
            int carry = 0;//进位
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (l1 != null || l2 != null || carry > 0) {
                int sum = carry;
                sum += l1 == null ? 0 : l1.val;
                sum += l2 == null ? 0 : l2.val;
                ListNode node = new ListNode(sum % 10);
                cur.next = node;
                cur = node;
                carry = sum / 10;
                if(l1 != null) l1 = l1.next;
                if(l2 != null) l2 = l2.next;
            }
            return dummy.next;
        }
    }

234，回文链表，easy

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true
  • 方法一：借助栈。
    • 思路：将链表节点值放入栈并统计链表长度，循环 l/2 次（只需比较前一半节点值），如果链表的头部值与栈弹出的值不相等，返回false；否则节点右移，最终返回true。
    • 代码：
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        //将节点值放入栈
        int length = 0;
        while(temp != null){
            stack.push(temp.val);
            temp = temp.next;
            length++;
        }
        
        length /= 2;
        while(length-- > 0){
            if(stack.pop() != head.val){
               return false;
            }
            head = head.next;
        }
        return true;
    }
}
  • 方法二：将链表节点值转为集合存储，再使用双指针-头尾指针。
    • 代码：
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while(left < right){
            if(!list.get(left).equals(list.get(right)))
                return false;
            else{
            left++;
            right--;
            }
        }
        return true;
    } 
}
  • 错误点：if(list.get(left) != list.get(right)) 错误
    • Integer是对象，比较两个对象相等要用equals
    • 使用 == 比较Integer类型时，默认缓存 -128 ~ 127，超过此范围会new新对象，两个对象地址不一样则返回false
  • 方法三：快慢指针。
    • 思路：找到中间节点，将后半段链表进行反转，再比较反转后的链表与原链表前半段的值。
    • 代码：
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode middle = getMiddle(head);//链表中点，如果长度是偶数，返回第 l/2 - 1 个节点
        ListNode newHead = reverse(middle.next);//反转后半部分链表
        //比较前半部分和后半部分链表的节点值
        while(newHead != null){
            if(head.val != newHead.val){
                return false;
            }
            else{
                head = head.next;
                newHead = newHead.next;
            }
        }
        return true;
    } 
    public ListNode getMiddle(ListNode head){
        ListNode left = head;
        ListNode right = head;
        while(right.next != null && right.next.next != null){
            left = left.next;
            right = right.next.next;
        }
        return left;
    }
    //返回链表的中间节点
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode temp = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

725，分隔链表，middle

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

  • 方法一：拆分链表。

    • 思路：分类讨论。
      • 如果链表为空，返回 k 个空节点组成的节点数组。
      • 如果链表长度l <= k，前 l 个元素是单个节点，后 l - k 个元素为空。
      • 如果链表长度l > k，每部分至少有 l / k 个节点，前 l % k 部分节点数 + 1。再将原链表分部分存储在结果数组中，每部分为一个链表，部分之间要断开连接。
    • 代码：
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        if(root == null) return new ListNode[k];
        ListNode[] res = new ListNode[k];
        int length = getLength(root);
        if(length <= k){
            for(int i = 0; i < length; ){
                ListNode temp = root.next;
                root.next = null;
                res[i++] = root;
                root = temp;
            }
            for(int i = length; i < k; i++){
                res[i] = null;
            }
        }
        else if(length > k){
        //length 比 k 大时 每部分存放 l/k 个节点 , 前 l%k 部分存放 l/k+1 个节点
        int n = length / k;
        int m = length % k;
        int[] counts = new int[k];//记录每部分存储元素个数，[4][3][3]
        for(int i = 0; i < k; i++){
            counts[i] = m-- > 0 ? n + 1: n;
        }
        ListNode cur = root;
        //将节点存储到数组中 counts[0]=4
        for(int i = 0; i < k; i++){
            res[i] = cur;
            //跳到每部分最末节点 1->2->3->4
            for(int j = 0; j < counts[i] - 1; j++){
                cur = cur.next;
            }
            //断开每部分之间的连接
            ListNode temp = cur.next;
            cur.next = null;
            cur = temp;
         }
        }
        return res;
    }
    public int getLength(ListNode node){
        int length = 0;
        while(node != null){
            length++;
            node = node.next;
        }
        return length;
    }
}

328，奇偶链表，middle

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

  • 方法一：双指针，分离链表为奇链表、偶链表，再合并。
    • 代码：
class Solution {
    public ListNode oddEvenList(ListNode head) {
//双指针
        if(head == null) return head;
        
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        
        while(even != null && even.next != null){
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
------ 本文结束感谢您的阅读 ------