328. 奇偶链表

迷南。 2023-02-08 12:46 9阅读 0赞

题目链接：https://leetcode-cn.com/problems/odd-even-linked-list/

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

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

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

**题意：**  
给你一个链接，把奇数位置和偶数位置的节点分开，构成两个链表，然后拼接起来，达到分离奇数位和偶数位的目的

**思路**：这道题本质上还是链表的遍历问题。遍历单链表的核心代码是：

while (node != null) {
        
    	node = node.next
    }

1.  本题目先定义两个头结点，分别代表奇数位和偶数位链表
2.  然后遍历单链表
3.  把奇数位节点拼到奇数链表尾部，指针后移；
4.  把偶数位节点拼到偶数链表尾部，指针后移
5.  跳出循环后，把偶数拼接到奇数链表尾

这道题是中等难度，领会一下遍历单链表

java版本

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if (head == null) return head;
            ListNode odd = head;  // 奇数位链表的头结点（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;
        }
    }

再来一个golang版本

/**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func oddEvenList(head *ListNode) *ListNode {
        
        if head == nil || head.Next == nil {
        
            return head
        }
        var odd *ListNode = head
        var eventHead *ListNode = head.Next
        var even *ListNode = eventHead
        for even != nil && even.Next != nil {
        
            odd.Next = even.Next
            odd = odd.Next
            even.Next = odd.Next
            even = even.Next
        }
        odd.Next = eventHead
        return head
    }

go语言占用的内存就是小啊  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/c7a175d10b63400b9356164b6e043eb5.png