将链表分成两个和相等的子表

Question

我正试图将一个链表分成两个相等的子列表。这些子列表不需要由连续的元素组成。

我有一个链表

Eg.1
LinkedList={1,7,5,5,4}
should be divided into
LinkedList1={1,5,5}
LinkedList2={7,4}

都有与11相同的元素和。

Eg.2
LinkedList={42,2,3,2,2,2,5,20,2,20}
This should be divided into two list of equal sum i.e 50.
LinkedList1={42,3,5}
LinkedList2={2,2,2,2,20,2,20}

有人能提供一些伪代码来解决这个问题吗?

这是我到目前为止的想法:

1. 将链表元素相加，除以2

2. 现在，直到你的linkedlist1的和小于linkedlist/2的和继续推元素到linkedlist1

3. 如果不等于且小于linkedlist sum/2，移动到下一个元素，当前元素可以被推入linkedlist2。

Answer 1

这被称为分区问题。

有几种方法可以解决这个问题，但我将在下面提到最常见的两种方法(参见维基百科以获得关于每种方法或其他方法的更多详细信息)。

---

这可以用动态规划方法来解决，这基本上归结为，对于每个元素和值，包括或不包括该元素，并查找是否有一个子集求和到相应的值。更具体地说，我们有以下递归关系:

如果{ x1, ..., xj }的一个子集等于i和False，则p(i, j)为True。

如果p(i, j − 1)为True或p(i − xj, j − 1)为True，则

p(i, j)为True
p(i, j)为False，否则

则p(N/2, n)告诉我们子集是否存在。

运行时间为O(Nn)，其中n为输入集合中元素的个数，N为输入集合中元素的和。

---

"approximate"贪心方法(不一定要找到一个等和分区)是非常直接的——它只需要把每个元素都放到一个和最小的集合中。下面是伪代码:

INPUT:  A list of integers S
OUTPUT: An attempt at a partition of  S into two sets of equal sum
1  function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort  S in descending order
5     for i in S:
6        if sum(A) <= sum(B)
7           add element i to set A
8        else
9           add element i to set B
10    return {A, B}

运行时间为O(n log n)