LeetCode 328——奇偶链表（JAVA）（奇偶排序链表）

25-01-29 23

这篇文章主要围绕LeetCode328——奇偶链表和JAVA展开，旨在为您提供一份详细的参考资料。我们将全面介绍LeetCode328——奇偶链表的优缺点，解答JAVA的相关问题，同时也会为您带来32

这篇文章主要围绕LeetCode 328——奇偶链表和JAVA展开，旨在为您提供一份详细的参考资料。我们将全面介绍LeetCode 328——奇偶链表的优缺点，解答JAVA的相关问题，同时也会为您带来328. 奇偶链表、Day 67/100 数据结构链表（8）——奇偶链表、Leecode 160.相交链表（Java 哈希表、双指针）、Leecode 206.反转链表（Java）的实用方法。

本文目录一览：

LeetCode 328——奇偶链表（JAVA）（奇偶排序链表）
328. 奇偶链表
Day 67/100 数据结构链表（8）——奇偶链表
Leecode 160.相交链表（Java 哈希表、双指针）
Leecode 206.反转链表（Java）

LeetCode 328——奇偶链表（JAVA）（奇偶排序链表）

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

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

说明:

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

直接上代码：

/**
 * 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)
            return null;
        if(head.next==null||head.next.next==null)
            return head;
        ListNode odd=head;
        ListNode even=head.next;
        ListNode evenhead=even;//此处的evenhead是链表奇偶化之后偶半链的第一个节点，在下买你的while循环中，evenhead一直处于无前驱节点状态
        while(odd.next!=null&&even.next!=null){
            odd.next=odd.next.next;
            even.next=even.next.next;
            odd=odd.next;
            even=even.next;
        }//经过while循环之后，实际上链表已经被切成两半了，一般是奇链表，一半是偶链表，其中保留了两个指针，一个是odd奇链表的最后一个元素，evenhead是偶链表的第一个节点。
        odd.next=evenhead;//将奇偶链表连接起来
        return head;
    }
}

算法思想：

1、根据奇偶数原则，首先将odd指向head，even指向head.next，同时evenhead也指向head.next。

2、接下来，分别以odd开头“删除”偶数链表，以even 开头删除奇数链表。这样一来将整个链表拆分为两个链表。同时保留了三个节点，分别是odd（奇数链表的最后一个节点），even（偶数链表最后一个节点），evenhead（偶数链表第一个节点）。

3、最后只需将奇偶链表连接起来即可。odd.next=evenhead，大功告成！！！

算法分析：

此算法是在原地修改，并没有开辟新的存储空间，因此空间复杂度是O(1);

对于时间复杂度来说，需要迭代整个链表，因此时间复杂度是O(nodes)。

328. 奇偶链表

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

示例 1:

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

 1 public class OddEvenLinkedList {
 2     static class ListNode {
 3         int val;
 4         ListNode next;
 5         ListNode(int x) {
 6             val = x;
 7         }
 8     }
 9     public ListNode oddEvenList1(ListNode head) {
10         ListNode cur = head.next;
11         ListNode curOdd = head;
12         while(cur != null && cur.next !=null) {
13             ListNode odd = cur.next;  //新的奇数位结点
14             ListNode next = cur.next.next;  //下一个被操作的偶数位结点
15             ListNode even = curOdd.next;  //当前奇数位后的偶数结点
16             cur.next = next;  //当前偶数位结点指向下一个被操作的偶数位结点
17             curOdd.next = odd;  //当前奇数位结点指向新的奇数位结点
18             odd.next = even;  //新奇数位结点指向当前奇数位后的偶数结点
19             cur = next; //开始新的循环
20             curOdd = odd;
21         }
22         return head;       
23     }    
24     public ListNode oddEvenList2(ListNode head) {
25         if (head == null) {
26             return head;
27         }
28         ListNode odd = head;
29         ListNode even = head.next;
30         ListNode evenHead = even;  //记录第一个偶数位结点
31         while (even != null && even.next != null) {
32             odd.next = odd.next.next;
33             odd = odd.next;
34             even.next = even.next.next;
35             even = even.next;
36         }
37         odd.next = evenHead;  //奇数位结点最后一个结点指向记录的第一个偶数位结点，形成新的链表
38         return head;
39     }
40 
41 }

Day 67/100 数据结构链表（8）——奇偶链表

（一）需求

今儿还是链表中的一个算法——奇偶链表。

（二）奇偶链表

1、问题描述

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

Demo1:

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

Demo2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

2、思路:

定义一个新的额外空间
逐个遍历原链表
将符合奇偶数据的节点，放到对应声明的变量中

fig1

3、代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function oddEvenList(head: ListNode | null): ListNode | null {
  if(head === null){
    return head
  }
  let evenHead = head.next; // 定义偶数头结点
  let odd = head // 定义奇数头结点
  let 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
};

空间复杂度将是 O(1)
时间复杂度将是 O(n)

以上

参考链接

https://leetcode.cn/leetbook/...

写在最后的话

学习路上，常常会懈怠

《有想学技术需要监督的同学嘛~》
https://mp.weixin.qq.com/s/Fy...

Leecode 160.相交链表（Java 哈希表、双指针）

找两个链表第一次指针相同的地方想法：（本来是没有的，因为没读懂题目描述= =） 1.两个指针，长的先走（长减短相差的长度）这么多的步数，然后就可以开始比较指针，直到指向为空，期间如果指针相同，返回该节点，如果链表未相交，则返回的是null 可是这是链表啊！没法知道长度！！！ 2.hashset 将长链表的元素放入set，从短链表的头部开始，依次向后判断该元素是否在set中，如果是则表明两个链表相交，返回该点，若到最后都没有，则两个链表不相交，返回null

 1 /**
 2 * DeFinition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode(int x) {
 7 *         val = x;
 8 *         next = null;
 9 *     }
10 * }
11 */
12 public class Solution {
13     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14         if(headA == null||headB == null){
15             return null;
16         }
17         Set setList = new HashSet<>();
18         while(headA!=null){
19             setList.add(headA);
20             headA = headA.next;
21         }//将一链表的元素放入set
22         while(headB!=null){
23             if(setList.contains(headB)){
24                 return headB;
25             }
26             headB = headB.next;
27         }//从另一链表的头部开始，依次向后判断该元素是否在set中，如果是则表明两个链表相交，返回该点，若到最后都没有，则两个链表不相交，返回null
28         return null;
29     }
30 }

3.双指针根据等长原理，指针相遇时返回该点

如果像左边情况一样，两链表相加，长链表长度6，短链表长度4，相交长度2。甲从长链表头开始走，乙从短链表头开始走，甲乙走到空时从另一个链表的头开始走，甲走了4+2+2=乙走了2+2+4，之后甲乙相遇，返回该点，如果向右边情况一样，两个长度不等且不相交的链表，甲走6+3=乙走3+6，之后甲乙相遇，在null，返回null。该方法就是：【当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：每步操作需要同时更新指针 pA 和 pB 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点当指针 pA 和 pB 相遇时返回该节点。都为空时，返回 null 作者：dodo_1202 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/c-jiao-cha-bian-li-shuang-zhi-zhen-by-do-6eb1/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。】使用for进行一个经过一次指针为空的循环（n<3）{ 判断pa pb是否相遇，若相遇返回该点，若不相遇继续下面： pa pb向前移动 if（pa此时为空），则pa移到headb重新开始，中间变量 n+1； if（pb此时为空），则pb移到heada重新开始，中间变量 n+1； } 到了这里说明双链表不相交返回null

Leecode 206.反转链表（Java）

想法： 1.设链表长度为n，如5，头节点head，则最后一个元素位置为head-1。 错误，发现行不通，此为链表非数组，存储位置不连续 2.设两个指针p,q，让p,q指向head，再让p指向head的下一个，若不为空，则交换pq（45321），接着q指向p，p指向p的下一个，若不为空则交换(43521)，继续，直至p指向空，此时（43215），此时迭代了1次。迭代次数为链表的长度-1 错误，理解题意错了，不是要求反向排序，而是链接的箭头逆序 ----查看答案和思路，重新整理迭代：

设三指针，其中p指针所指是算法中欲指向的位置，s指针是作为中间变量给p指针挪动位置和反转，q指针起的作用是前进初始：p指向null，s和q指向head 当q.next不为空时，令q=q.next（向前移）；s.next=p（反转）；p=s（p移动位置向前）；s=q（s移动向前）；当q.next为空，说明已经到了最后一个元素，此时直接将s.next=p（反转）；或者也可以将q.next=p，也可以反转，反正s和q此时都是指向最后一个元素

 1 /**
 2 * DeFinition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11 class Solution {
12     public ListNode reverseList(ListNode head) {
13         ListNode p,s,q=new ListNode();
14         p = null;
15         s = head;
16         q =head;
17         while (q.next != null){
18             q = q.next;
19             s.next = p;
20             p = s;
21             s = q;
22         }
23         q.next = p;
24         head = s;
25     return head;
26     }
27 }

关于LeetCode 328——奇偶链表和JAVA的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于328. 奇偶链表、Day 67/100 数据结构链表（8）——奇偶链表、Leecode 160.相交链表（Java 哈希表、双指针）、Leecode 206.反转链表（Java）等相关内容，可以在本站寻找。

本文标签：