链表系列题目合集：Leetcode链表题目 建议先看本人博客中算法通关面试40讲中的链表部分题目。 方法：

使用prev前置指针，用于反转链表全部或部分类的题目使用快慢指针，用于判断链表内部是否有环类题目，以及删除节点题目环形问题找到环的入口方法：快慢指针第一次相遇后，快指针从头部再与慢指针相遇的位置获得链表的中间节点，使用快慢指针，快指针走两步，慢指针走一步，快指针next为null或者为null时，慢指针指向中间节点双指针连接链表法，用于查找相交链表

Leetcode-23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

解法：1. 暴力算法，将所有节点放在一个数组中，排序之后输出，时间O(NlogN)，N是节点总数。2. 分治，将k个list两两组合，用图来表示如下，时间复杂度O(NlogK)，k是链表的条数，空间复杂度O（1）

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists==null || lists.length==0) return null; int amount = lists.length; int i = 1; while (i < amount) { for (int j=0;j+i<amount;j += i*2) { lists[j] = this.mergeTwoLists(lists[j], lists[j+i]); } i *= 2; } return lists[0]; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode pointer = new ListNode(0); ListNode head = pointer; while (l1!=null && l2!=null) { if (l1.val > l2.val) { pointer.next = l2; l2 = l2.next; } else { pointer.next = l1; l1 = l1.next; } pointer = pointer.next; } if (l1==null) { pointer.next = l2; } else { pointer.next = l1; } return head.next; } } Python class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ amount = len(lists) interval = 1 while interval < amount: for i in range(0, amount - interval, interval * 2): lists[i] = self.merge2Lists(lists[i], lists[i + interval]) interval *= 2 return lists[0] if amount > 0 else lists def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next if not l1: point.next=l2 else: point.next=l1 return head.next

Leetcode-82. 删除排序链表中的重复元素 II

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

示例 1:

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

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

解法：只要节点的左右值不同，那么节点就是一个可用节点，否则不是

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) return head; ListNode pointer = new ListNode(0==head.val? 1: 0); ListNode pre = pointer, l = pointer; while (head != null) { while (head!=null && (pre.val==head.val || (head.next!=null && head.val==head.next.val))) { pre = head; head = head.next; } pointer.next = head; pointer = pointer.next; pre = head; head = head==null? head: head.next; } return l.next; } }

Leetcode-61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

解法：很简单，找到rotate的位置和null前的位置，进行rotate即可

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) return null; int length = 1; ListNode tmp = head, pre = tmp, cur = tmp; while (tmp.next != null) { //Get the total length tmp = tmp.next; length++; } k = k%length; if (k==0) return head; for (int i=0;i<length-k-1;i++) { //Get the length-k%length th node pre = pre.next; } cur = pre.next; // rotate pre.next = null; tmp.next = head; return cur; } }

Leetcode-86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5

解法：用两个链表分别存储小于x的和不小于的，最后连接一下就可以

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode partition(ListNode head, int x) { ListNode pre = new ListNode(0); ListNode after = new ListNode(0); ListNode dummy1 = pre; ListNode dummy2 = after; while (head !=null) { if (head.val<x) { pre.next = head; pre = pre.next; } else{ after.next = head; after = after.next; } head = head.next; } after.next = null; pre.next = dummy2.next; return dummy1.next; } }

Leetcode-92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

解法：我这里采用的办法是分开再连接，将要进行反转的部分拆出来，利用了头尾节点在翻转中的被调转过来的特性。这道题可以打个星号着重看一下，时间复杂度O（N），空间复杂度O（1）。

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (head==null || head.next==null) return head; ListNode pre = new ListNode(0); pre.next = head; ListNode dummy = pre; ListNode cur = head; // 想要将pre移至m的前一个节点，cur移至n节点上，现在pre和cur相差1节点，达到目的时相差n-m+1节点，所以cur需要移动n-m个节点才能保持两者间距为n-m+1 for (int i=0;i<n-m;i++) { cur = cur.next; } // 同时平移至目标位置 for (int i=0;i<m-1;i++) { pre = pre.next; cur = cur.next; } // 记录下pre当前的位置 ListNode node = pre; // 记录cur的下一个位置，因为reverse之后还要连接回去 ListNode next = cur.next; cur.next = null; // 将pre调整到下一个节点进行翻转，传入的头尾节点是pre和cur，翻转之后的头尾节点是cur和pre，再进行重新连接即可 pre = pre.next; // node.next = this.reverseList(pre); // 与node.next = cur是一个效果 this.reverseList(pre); // 重新连接 node.next = cur; pre.next = next; return dummy.next; } public ListNode reverseList(ListNode head) { ListNode pre = null; while (head != null) { ListNode tmp = head.next; head.next = pre; pre = head; head = tmp; } return pre; } }

Leetcode-108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5

解法：利用中间节点使用递归，

Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums==null || nums.length==0) return null; return this.helper(nums, 0, nums.length-1); } public TreeNode helper(int[] nums, int left, int right) { int mid = (left+right) / 2; TreeNode p = new TreeNode(nums[mid]); if (mid != left) { p.left = this.helper(nums, left, mid-1); } if (mid != right) { p.right = this.helper(nums, mid+1, right); } return p; } }

Leetcode-109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9], 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5

解法：1. 使用链表的快慢指针找到中间元素，然后将中间元素作为root，左边右边分别使用递归变为二叉搜索树，最终返回root即可，时间复杂度O(NlogN)，空间复杂度O(logN)。2. 与上面的方法类似，不过是将链表转换成数组在进行操作，时间复杂度O(N)，空间复杂度O(N）

Java 链表 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private ListNode findMiddleElement(ListNode head) { ListNode prevPtr = head; ListNode slowPtr = prevPtr; ListNode fastPtr = prevPtr; while (fastPtr != null && fastPtr.next != null) { prevPtr = slowPtr; slowPtr = slowPtr.next; fastPtr = fastPtr.next.next; } prevPtr.next = null; return slowPtr; } public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } ListNode mid = this.findMiddleElement(head); TreeNode node = new TreeNode(mid.val); if (head == mid) { return node; } node.left = this.sortedListToBST(head); node.right = this.sortedListToBST(mid.next); return node; } }

数组

class Solution { public TreeNode sortedListToBST(ListNode head) { if (head==null) return null; ArrayList<Integer> lst = new ArrayList<Integer>(); lst = this.addList(head, lst); return this.helper(lst, 0, lst.size()-1); } public ArrayList<Integer> addList(ListNode head, ArrayList<Integer> lst) { ListNode tmp = head; while (tmp != null) { lst.add(tmp.val); tmp = tmp.next; } return lst; } public TreeNode helper(ArrayList<Integer> lst, int left, int right) { int mid = left + (right-left)/2; TreeNode root = new TreeNode(lst.get(mid)); if (mid != left) { root.left = this.helper(lst, left, mid-1); } if (mid != right) { root.right = this.helper(lst, mid+1, right); } return root; } }

Leetcode-138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 输入： {“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","next":{"id”:“2”,“next”:null,“random”:{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"2"}̲,"val":2},"rand…ref”:“2”},“val”:1}

解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

解法：深拷贝，要建立额外的node来进行保存，使用map判断对应的node是否之前建立过（因为有random），时间复杂度O(N)，空间复杂度O(N)

Java /* // Definition for a Node. class Node { public int val; public Node next; public Node random; public Node() {} public Node(int _val,Node _next,Node _random) { val = _val; next = _next; random = _random; } }; */ class Solution { HashMap<Node, Node> visited = new HashMap<>(); public Node copyRandomList(Node head) { if (head==null) return null; Node oldNode = head; Node newNode = new Node(oldNode.val, null, null); this.visited.put(oldNode, newNode); while (oldNode != null) { newNode.next = this.getNode(oldNode.next); newNode.random = this.getNode(oldNode.random); oldNode = oldNode.next; newNode = newNode.next; } return this.visited.get(head); } public Node getNode(Node node) { if (node==null) return null; if (this.visited.containsKey(node)) { return this.visited.get(node); } else { this.visited.put(node, new Node(node.val, null, null)); return this.visited.get(node); } } }

Leetcode-143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解法：1. 先从中间拆开，翻转后面的，在挨个插入前面的。2. 每次都把最后一个元素放在第一个元素后面

递归挨个插入

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void reorderList(ListNode head) { if (head==null) return; ListNode slow = head; ListNode fast = slow; ListNode pre = slow; while (fast!=null && fast.next!=null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; ListNode l1 = head; ListNode l2 = null; // 翻转后的头部 while (slow!=null) { ListNode tmp = slow.next; slow.next = l2; l2 = slow; slow = tmp; } head = this.reorder(l1, l2); } public ListNode reorder(ListNode head1, ListNode head2) { if (head1==null && head2==null) { return null; } else if (head1 == null) { return head2; } else { ListNode next1 = head1.next; ListNode next2 = head2.next; ListNode dummy = head1; head1.next = head2; head2.next = this.reorder(next1, next2); return dummy; } } } class Solution { public void reorderList(ListNode head) { // Nothing to do if the list has 2 or fewer nodes if (head == null || head.next == null || head.next.next == null) return; ListNode slast = head; // second last node ListNode last = head.next; // last node while (last.next != null) { last = last.next; slast = slast.next; } // Insert the last node right after the first node ListNode tmp = head.next; head.next = last; last.next = tmp; // Second last node should point to null otherwise there would be a cycle slast.next = null; reorderList(tmp); } }

Leetcode-147. 对链表进行插入排序

对链表进行插入排序。 在这里插入图片描述

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。

示例 1：

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

示例 2：

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

解法：此题考察的是插入算法，每次链表的左边都保持有序，在右边遍历元素插入左边的合适的位置，时间复杂度O(N)，空间复杂度O(N)

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode insertionSortList(ListNode head) { if (head==null || head.next==null) return head; ListNode pre = new ListNode(head.val); ListNode l ; head = head.next; while (head != null) { ListNode next = head.next; head.next = null; pre = this.insertNode(pre, head); head = next; } return pre; } public ListNode insertNode(ListNode head, ListNode node) { if (head == null) { head = node; return head; } // 设置两个tmp是为了不改变head和node的结构 ListNode tmp1 = head; ListNode tmp2 = node; ListNode pre = new ListNode(0); pre.next = tmp1; ListNode dummy = pre; while (tmp1 != null) { // 如果大于插入值的位置立马插入，并返回 if (tmp1.val > tmp2.val) { ListNode next = tmp1.next; pre.next = tmp2; tmp2.next = tmp1; tmp1 = next; return dummy.next; } else{ // 没找到的话继续向下找 pre = tmp1; tmp1 = tmp1.next; } } // 如果到了最后还没有找到，说明插入的节点的值是最大的，插入到最后 pre.next = node; node.next = null; return dummy.next; } }

Leetcode-148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4 示例 2:

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

解法：由O(NlogN)联想到可能是归并排序（merge sort），使用递归即可。

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { if (head==null || head.next==null) return head; ListNode pre = head; ListNode slow = head; ListNode fast = head; while (fast!=null && fast.next!=null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; ListNode l1 = this.sortList(head); ListNode l2 = this.sortList(slow); return this.mergeTwoList(l1, l2); } public ListNode mergeTwoList(ListNode l1, ListNode l2) { if (l1==null || l2==null) { return l1==null?l2:l1; } ListNode pointer = new ListNode(0); ListNode dummy = pointer; while (l1!=null && l2!=null) { if (l1.val<l2.val) { pointer.next = l1; l1 = l1.next; } else { pointer.next = l2; l2 = l2.next; } pointer = pointer.next; } if (l1==null) { pointer.next = l2; } else { pointer.next = l1; } return dummy.next; } }

Leetcode-160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.在返回结果后，两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法：1. 使用set添加第一条链路的元素，然后在第二个链路中查找有无，时间复杂度O(M+N)，空间复杂度O(M) 2. 双指针法。创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。当 pA到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点。若在某一时刻 pApA 和 pBpB 相遇，则 pA/pB为相交结点。时间复杂度O(M+N)，空间复杂度O(1)

Java 使用Set /** * 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) { if (headA==null || headB==null) { return null; } Set<ListNode> set = new HashSet<>(); ListNode l1 = headA; ListNode l2 = headB; while (l1 != null) { set.add(l1); l1 = l1.next; } while (l2 != null) { if (set.contains(l2)) return l2; l2 = l2.next; } return null; } }

使用双指针法

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode ha = headA, hb = headB; while (ha != hb) { ha = ha != null ? ha.next : headB; hb = hb != null ? hb.next : headA; } return ha; } }

Leetcode-203. 移除链表元素

删除链表中等于给定值 val 的所有节点。 示例:

输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5

解法：相等就跳过，非常简单的题

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeElements(ListNode head, int val) { if (head==null) return null; ListNode l1 = new ListNode(0==val?-1:0); l1.next = head; ListNode l2 = l1; ListNode dummy = l1; while (l1 != null) { if (l1.val != val) { l2 = l1; l1 = l1.next; } else { ListNode tmp = l1.next; l2.next = tmp; l1 = tmp; } } return dummy.next; } }

Leetcode-234. 回文链表

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

示例 1:

输入: 1->2 输出: false

示例 2:

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

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法：使用快慢指针找到中点，将后半条链表翻转再与前半条链表一一比较，时间复杂度O(N)

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head==null || head.next==null) return head; ListNode l1 = head; ListNode pre = null; while (l1!=null) { ListNode tmp = l1.next; l1.next = pre; pre = l1; l1 = tmp; } return pre; } public boolean isPalindrome(ListNode head) { if (head==null || head.next==null) return true; ListNode pre = head; ListNode slow = pre; ListNode fast = pre; ListNode head1 = pre; while (fast!=null && fast.next!=null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; ListNode head2 = this.reverseList(slow); while (head1 != null && head2!=null) { if (head1.val != head2.val) return false; head1 = head1.next; head2 = head2.next; } return true; } }

Leetcode-328. 奇偶链表

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

请尝试使用原地算法完成。你的算法的空间复杂度应为 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

说明:

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

解法：分别记录奇偶节点，奇节点连接在一起，偶节点连接在一起，最后将偶链表连接在奇链表之后，时间复杂度O(N)，空间复杂度O(1)

Java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode oddEvenList(ListNode head) { if (head==null || head.next==null) return head; ListNode odd = head; ListNode evenHead = head.next; ListNode 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; } }