如何将列表分割为两个等长子列表？（附Prolog代码实现需求）

需求很明确：把一个长度为偶数的列表分割成两个长度完全相同的子列表，比如输入[1,2,3,4,5,6,7,8,9,10]，要得到[1,2,3,4,5]和[6,7,8,9,10]。先看看你现有代码的问题，再给出两种可行的实现方案。

你的初始代码问题分析 #

你写的len函数是正确的，能准确计算列表长度。但注释掉的split规则逻辑不对：

%split([A|T],[A|T1],[B|T2]):-
%   split(T,T1,T2).

这个规则会把列表元素交替分配到两个子列表里，比如测试split([1,2,3,4,5,6],Lst1,Lst2)，得到的会是Lst1=[1,3,5]、Lst2=[2,4,6]，完全不符合“前后两半等长”的需求。

方案一：先算长度再分割（直观易理解） #

利用你已有的len函数，先算出列表总长度，取一半后提取前半部分，剩下的就是后半部分。需要补充一个take函数来提取前N个元素：

% 计算列表长度（你的原有代码）
len([],0).
len([X|L],N):-len(L,M),N is M+1.

% 提取列表的前N个元素
take(0, _, []).
take(N, [X|Xs], [X|Ys]) :-
    N > 0,
    N1 is N - 1,
    take(N1, Xs, Ys).

% 核心分割谓词：仅处理长度为偶数的列表
split_equal(List, L1, L2) :-
    len(List, TotalLen),
    TotalLen mod 2 =:= 0,  % 确保列表长度是偶数，否则无法分割
    HalfLen is TotalLen // 2,
    take(HalfLen, List, L1),
    append(L1, L2, List).  % 通过append确认L2是List去掉L1后的剩余部分

测试示例 #

?- split_equal([1,2,3,4,5,6,7,8,9,10], L1, L2).
L1 = [1, 2, 3, 4, 5], L2 = [6, 7, 8, 9, 10].

逻辑解释 #

1. 先调用len计算列表总长度，判断是否为偶数（如果是奇数，谓词直接失败）；
2. 计算出一半长度HalfLen；
3. 用take提取前HalfLen个元素作为L1；
4. 用append反向推导得到L2——因为L1拼接L2等于原列表，所以剩下的部分就是L2。

方案二：单遍历递归分割（高效） #

不需要提前计算长度，用“快慢指针”的思路递归遍历列表：快指针每次走两步，慢指针每次走一步，当快指针走到末尾时，慢指针刚好停在列表中间，此时就能拆分出前后两半。

% 辅助谓词：fast指针每次走2步，slow指针每次走1步，直到fast为空
split_helper([], Slow, [], Slow).
split_helper([_,_|FastRest], [X|SlowRest], [X|L1], L2) :-
    split_helper(FastRest, SlowRest, L1, L2).

% 核心分割谓词
split_equal(List, L1, L2) :-
    split_helper(List, List, L1, L2).

测试示例 #

?- split_equal([1,2,3,4,5,6,7,8,9,10], L1, L2).
L1 = [1, 2, 3, 4, 5], L2 = [6, 7, 8, 9, 10].

逻辑解释 #

1. split_helper的第一个参数是快指针列表，第二个是慢指针列表，第三、第四个参数分别收集前后两半；
2. 每次递归，快指针去掉前两个元素，慢指针去掉第一个元素并把这个元素加入L1；
3. 当快指针为空时，慢指针剩下的元素就是L2，此时L1已经收集了前半部分所有元素。

这个方法只需要遍历列表一次，比方案一效率更高，适合处理长列表。

内容的提问来源于stack exchange，提问作者Дима Николаев