解题思路

这是一道链表操作题目，主要思路如下：

  1. 链表处理分为三步：

    • 找到链表中点（使用快慢指针）
    • 反转后半部分链表
    • 合并前半部分和反转后的后半部分

  2. 具体步骤：

    • 使用快慢指针找到中点
    • 从中点开始反转后半部分链表
    • 将反转后的后半部分链表节点依次插入到前半部分相应位置

  3. 边界情况处理：

    • 空链表直接返回
    • 单节点链表直接输出
    • 注意奇偶长度的处理

代码

#include <iostream>
#include <string>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reorderList(string& s) {
        // 构建链表
        ListNode* head = new ListNode(-1);
        ListNode* curr = head;
        int num = 0;
        
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == ',') {
                curr->next = new ListNode(num);
                curr = curr->next;
                num = 0;
            } else {
                num = num * 10 + (s[i] - '0');
            }
        }
        curr->next = new ListNode(num);
        
        // 处理特殊情况
        if(head->next == NULL) return NULL;
        if(head->next->next == NULL) return head->next;
        
        // 找到中点
        ListNode *slow = head->next, *fast = head->next;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分
        ListNode *pre = NULL, *curr = slow->next;
        while(curr) {
            ListNode* next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        slow->next = NULL;
        
        // 合并两部分
        ListNode *p1 = head->next, *p2 = pre;
        while(p2) {
            ListNode *next1 = p1->next;
            ListNode *next2 = p2->next;
            p1->next = p2;
            p2->next = next1;
            p1 = next1;
            p2 = next2;
        }
        
        return head->next;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        Solution solution = new Solution();
        ListNode result = solution.reorderList(s);
        
        // 输出结果
        while(result != null) {
            System.out.print(result.val);
            if(result.next != null) System.out.print(",");
            result = result.next;
        }
    }
    
    static class Solution {
        public ListNode reorderList(String s) {
            // 构建链表
            String[] nums = s.split(",");
            ListNode head = new ListNode(-1);
            ListNode curr = head;
            
            for(String num : nums) {
                curr.next = new ListNode(Integer.parseInt(num));
                curr = curr.next;
            }
            
            // 处理特殊情况
            if(head.next == null) return null;
            if(head.next.next == null) return head.next;
            
            // 找到中点
            ListNode slow = head.next, fast = head.next;
            while(fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            // 反转后半部分
            ListNode pre = null;
            curr = slow.next;
            while(curr != null) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            slow.next = null;
            
            // 合并两部分
            ListNode p1 = head.next, p2 = pre;
            while(p2 != null) {
                ListNode next1 = p1.next;
                ListNode next2 = p2.next;
                p1.next = p2;
                p2.next = next1;
                p1 = next1;
                p2 = next2;
            }
            
            return head.next;
        }
    }
}

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorder_list(s):
    # 构建链表
    nums = list(map(int, s.split(',')))
    head = ListNode(-1)
    curr = head
    
    for num in nums:
        curr.next = ListNode(num)
        curr = curr.next
    
    # 处理特殊情况
    if not head.next: return None
    if not head.next.next: return head.next
    
    # 找到中点
    slow = fast = head.next
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 反转后半部分
    pre = None
    curr = slow.next
    while curr:
        next_node = curr.next
        curr.next = pre
        pre = curr
        curr = next_node
    slow.next = None
    
    # 合并两部分
    p1 = head.next
    p2 = pre
    while p2:
        next1 = p1.next
        next2 = p2.next
        p1.next = p2
        p2.next = next1
        p1 = next1
        p2 = next2
    
    return head.next

def main():
    s = input().strip()
    result = reorder_list(s)
    
    # 输出结果
    output = []
    while result:
        output.append(str(result.val))
        result = result.next
    print(','.join(output))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：快慢指针 + 链表反转
  • 时间复杂度： - 需要遍历链表多次
  • 空间复杂度： - 只需要常数级别的额外空间