面试问题：合并两个单独链接的列表而不创建新节点
https://stackoverflow.com//questions/10707352
-
13-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
这是一个在面试考试期间询问的编程问题。 “您有两个已对其进行分类的单独链接列表，您必须合并它们并在不创建任何新额外节点的情况下返回新列表的头部。返回的列表也应按”
“方法签名是： 节点Mergelists（节点列表1，节点列表2）;
节点类如下：
class Node{
int data;
Node next;
}
我尝试了许多解决方案，但没有创建额外的节点螺钉。请帮忙。
解决方案
Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.data < list2.data) {
list1.next = MergeLists(list1.next, list2);
return list1;
} else {
list2.next = MergeLists(list2.next, list1);
return list2;
}
}
其他提示
不需要递归以避免分配新节点：
Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
Node head;
if (list1.data < list2.data) {
head = list1;
} else {
head = list2;
list2 = list1;
list1 = head;
}
while(list1.next != null) {
if (list1.next.data > list2.data) {
Node tmp = list1.next;
list1.next = list2;
list2 = tmp;
}
list1 = list1.next;
}
list1.next = list2;
return head;
}
Node MergeLists(Node node1, Node node2)
{
if(node1 == null)
return node2;
else (node2 == null)
return node1;
Node head;
if(node1.data < node2.data)
{
head = node1;
node1 = node1.next;
else
{
head = node2;
node2 = node2.next;
}
Node current = head;
while((node1 != null) ||( node2 != null))
{
if (node1 == null) {
current.next = node2;
return head;
}
else if (node2 == null) {
current.next = node1;
return head;
}
if (node1.data < node2.data)
{
current.next = node1;
current = current.next;
node1 = node1.next;
}
else
{
current.next = node2;
current = current.next;
node2 = node2.next;
}
}
current.next = NULL // needed to complete the tail of the merged list
return head;
}
以下是如何合并两个排序链接列表a和b：
的算法while A not empty or B not empty:
if first element of A < first element of B:
remove first element from A
insert element into C
end if
else:
remove first element from B
insert element into C
end while
这里c将是输出列表。
看ma，没有递归！
struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;
for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
if (cmp(one,two) <=0) { *tail = one; one=one->next; }
else { *tail = two; two=two->next; }
}
*tail = one ? one: two;
return result;
}
迭代可以如下完成。复杂性= o（n）
public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
LLNode mergedNode ;
LLNode tempNode ;
if (nodeA == null) {
return nodeB;
}
if (nodeB == null) {
return nodeA;
}
if ( nodeA.getData() < nodeB.getData())
{
mergedNode = nodeA;
nodeA = nodeA.getNext();
}
else
{
mergedNode = nodeB;
nodeB = nodeB.getNext();
}
tempNode = mergedNode;
while (nodeA != null && nodeB != null)
{
if ( nodeA.getData() < nodeB.getData())
{
mergedNode.setNext(nodeA);
nodeA = nodeA.getNext();
}
else
{
mergedNode.setNext(nodeB);
nodeB = nodeB.getNext();
}
mergedNode = mergedNode.getNext();
}
if (nodeA != null)
{
mergedNode.setNext(nodeA);
}
if (nodeB != null)
{
mergedNode.setNext(nodeB);
}
return tempNode;
}
Node mergeList(Node h1, Node h2) {
if (h1 == null) return h2;
if (h2 == null) return h1;
Node head;
if (h1.data < h2.data) {
head = h1;
} else {
head = h2;
h2 = h1;
h1 = head;
}
while (h1.next != null && h2 != null) {
if (h1.next.data < h2.data) {
h1 = h1.next;
} else {
Node afterh2 = h2.next;
Node afterh1 = h1.next;
h1.next = h2;
h2.next = afterh1;
if (h2.next != null) {
h2 = afterh2;
}
}
}
return head;
}
可以在不创建额外节点的情况下完成，只需另一个通过传递到参数的节点（节点temp）。
private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
if(nodeList1.data <= nodeList2.data){
temp = nodeList1;
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
}
else{
temp = nodeList2;
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
}
return temp;
}
我想分享我的想法如何解决问题......我看到涉及递归的解决方案，它们非常惊人，是功能性和模块化思维的结果。我非常感谢分享。
我想补充一下，递归不适用于大点，堆栈呼叫将溢出;所以我决定尝试迭代方法......这就是我得到的。
代码非常自我解释，我添加了一些内联的评论来试图确保这一点。
如果你没有得到它，请通知我，我将提高可读性（也许我有一个误导对我自己代码的解释）。
import java.util.Random;
public class Solution {
public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {
T data;
Node next;
@Override
public int compareTo(Node<T> otherNode) {
return data.compareTo(otherNode.data);
}
@Override
public String toString() {
return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null");
}
}
public static Node merge(Node firstLeft, Node firstRight) {
combine(firstLeft, firstRight);
return Comparision.perform(firstLeft, firstRight).min;
}
private static void combine(Node leftNode, Node rightNode) {
while (leftNode != null && rightNode != null) {
// get comparision data about "current pair of nodes being analized".
Comparision comparision = Comparision.perform(leftNode, rightNode);
// stores references to the next nodes
Node nextLeft = leftNode.next;
Node nextRight = rightNode.next;
// set the "next node" of the "minor node" between the "current pair of nodes being analized"...
// ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision.
comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min;
if (comparision.min == leftNode) {
leftNode = nextLeft;
} else {
rightNode = nextRight;
}
}
}
/** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */
private static class Comparision {
private final Node min;
private final Node max;
private Comparision(Node min, Node max) {
this.min = min;
this.max = max;
}
private static Comparision perform(Node a, Node b) {
Node min, max;
if (a != null && b != null) {
int comparision = a.compareTo(b);
if (comparision <= 0) {
min = a;
max = b;
} else {
min = b;
max = a;
}
} else {
max = null;
min = (a != null) ? a : b;
}
return new Comparision(min, max);
}
}
// Test example....
public static void main(String args[]) {
Node firstLeft = buildList(20);
Node firstRight = buildList(40);
Node firstBoth = merge(firstLeft, firstRight);
System.out.println(firstBoth);
}
// someone need to write something like this i guess...
public static Node buildList(int size) {
Random r = new Random();
Node<Integer> first = new Node<>();
first.data = 0;
first.next = null;
Node<Integer> current = first;
Integer last = first.data;
for (int i = 1; i < size; i++) {
Node<Integer> node = new Node<>();
node.data = last + r.nextInt(5);
last = node.data;
node.next = null;
current.next = node;
current = node;
}
return first;
}
}
一个简单的迭代解决方案。
Node* MergeLists(Node* A, Node* B)
{
//handling the corner cases
//if both lists are empty
if(!A && !B)
{
cout << "List is empty" << endl;
return 0;
}
//either of list is empty
else if(!A) return B;
else if(!B) return A;
else
{
Node* head = NULL;//this will be the head of the newList
Node* previous = NULL;//this will act as the
/* In this algorithm we will keep the
previous pointer that will point to the last node of the output list.
And, as given we have A & B as pointer to the given lists.
The algorithm will keep on going untill either one of the list become empty.
Inside of the while loop, it will divide the algorithm in two parts:
- First, if the head of the output list is not obtained yet
- Second, if head is already there then we will just compare the values and keep appending to the 'previous' pointer.
When one of the list become empty we will append the other 'left over' list to the output list.
*/
while(A && B)
{
if(!head)
{
if(A->data <= B->data)
{
head = A;//setting head of the output list to A
previous = A; //initializing previous
A = A->next;
}
else
{
head = B;//setting head of the output list to B
previous = B;//initializing previous
B = B->next;
}
}
else//when head is already set
{
if(A->data <= B->data)
{
if(previous->next != A)
previous->next = A;
A = A->next;//Moved A forward but keeping B at the same position
}
else
{
if(previous->next != B)
previous->next = B;
B = B->next; //Moved B forward but keeping A at the same position
}
previous = previous->next;//Moving the Output list pointer forward
}
}
//at the end either one of the list would finish
//and we have to append the other list to the output list
if(!A)
previous->next = B;
if(!B)
previous->next = A;
return head; //returning the head of the output list
}
}
我显示在迭代解决方案以下。递归解决方案将更紧凑，但由于我们不知道列表的长度，递归运行堆栈溢出的风险。
基本思想类似于合并排序的合并步骤;我们保留对应于每个输入列表的指针;在每次迭代时，我们向对应于较小元素的指针提前。然而，大多数人都绊倒了一个至关重要的差异。在合并排序中，由于我们使用结果数组，因此插入的下一个位置始终是结果数组的索引。对于链接列表，我们需要将指向指向排序列表的最后一个元素。指针可以从一个输入列表跳转到另一个输入列表，具体取决于哪一个具有当前迭代的较小元素。
与此，以下代码应该是不言自明的。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode first = l1;
ListNode second = l2;
ListNode head = null;
ListNode last = null;
while (first != null && second != null) {
if (first.val < second.val) {
if (last != null) {
last.next = first;
}
last = first;
first = first.next;
} else {
if (last != null) {
last.next = second;
}
last = second;
second = second.next;
}
if (head == null) {
head = last;
}
}
if (first == null) {
last.next = second;
}
if (second == null) {
last.next = first;
}
return head;
}
首先了解“而不创建任何新的额外节点”，因为我理解它并不意味着我不能指向现有节点的指针（s））。
您无法在不谈论现有节点的情况下实现它，即使您使用递归来实现相同，系统将为您创建指针作为调用堆栈。这就像告诉您在代码中避免的指针一样。
简单的函数来实现相同的，拍摄额外的指针：
typedef struct _LLNode{
int value;
struct _LLNode* next;
}LLNode;
LLNode* CombineSortedLists(LLNode* a,LLNode* b){
if(NULL == a){
return b;
}
if(NULL == b){
return a;
}
LLNode* root = NULL;
if(a->value < b->value){
root = a;
a = a->next;
}
else{
root = b;
b = b->next;
}
LLNode* curr = root;
while(1){
if(a->value < b->value){
curr->next = a;
curr = a;
a=a->next;
if(NULL == a){
curr->next = b;
break;
}
}
else{
curr->next = b;
curr = b;
b=b->next;
if(NULL == b){
curr->next = a;
break;
}
}
}
return root;
}
Node * merge_sort(Node *a, Node *b){
Node *result = NULL;
if(a == NULL)
return b;
else if(b == NULL)
return a;
/* For the first node, we would set the result to either a or b */
if(a->data <= b->data){
result = a;
/* Result's next will point to smaller one in lists
starting at a->next and b */
result->next = merge_sort(a->next,b);
}
else {
result = b;
/*Result's next will point to smaller one in lists
starting at a and b->next */
result->next = merge_sort(a,b->next);
}
return result;
}
Node MergeLists(Node list1, Node list2) {
//if list is null return other list
if(list1 == null)
{
return list2;
}
else if(list2 == null)
{
return list1;
}
else
{
Node head;
//Take head pointer to the node which has smaller first data node
if(list1.data < list2.data)
{
head = list1;
list1 = list1.next;
}
else
{
head = list2;
list2 = list2.next;
}
Node current = head;
//loop till both list are not pointing to null
while(list1 != null || list2 != null)
{
//if list1 is null, point rest of list2 by current pointer
if(list1 == null){
current.next = list2;
return head;
}
//if list2 is null, point rest of list1 by current pointer
else if(list2 == null){
current.next = list1;
return head;
}
//compare if list1 node data is smaller than list2 node data, list1 node will be
//pointed by current pointer
else if(list1.data < list2.data)
{
current.next = list1;
current = current.next;
list1 = list1.next;
}
else
{
current.next = list2;
current = current.next;
list2 = list2.next;
}
}
return head;
}
}
以下是一个完整的工作示例，它使用链接列表实现的java.util。您只需在Main（）方法中的下面的代码中可以复制粘贴代码。
LinkedList<Integer> dList1 = new LinkedList<Integer>();
LinkedList<Integer> dList2 = new LinkedList<Integer>();
LinkedList<Integer> dListMerged = new LinkedList<Integer>();
dList1.addLast(1);
dList1.addLast(8);
dList1.addLast(12);
dList1.addLast(15);
dList1.addLast(85);
dList2.addLast(2);
dList2.addLast(3);
dList2.addLast(12);
dList2.addLast(24);
dList2.addLast(85);
dList2.addLast(185);
int i = 0;
int y = 0;
int dList1Size = dList1.size();
int dList2Size = dList2.size();
int list1Item = dList1.get(i);
int list2Item = dList2.get(y);
while (i < dList1Size || y < dList2Size) {
if (i < dList1Size) {
if (list1Item <= list2Item || y >= dList2Size) {
dListMerged.addLast(list1Item);
i++;
if (i < dList1Size) {
list1Item = dList1.get(i);
}
}
}
if (y < dList2Size) {
if (list2Item <= list1Item || i >= dList1Size) {
dListMerged.addLast(list2Item);
y++;
if (y < dList2Size) {
list2Item = dList2.get(y);
}
}
}
}
for(int x:dListMerged)
{
System.out.println(x);
}
递归方式（stefan答案的变体）
MergeList(Node nodeA, Node nodeB ){
if(nodeA==null){return nodeB};
if(nodeB==null){return nodeA};
if(nodeB.data<nodeA.data){
Node returnNode = MergeNode(nodeA,nodeB.next);
nodeB.next = returnNode;
retturn nodeB;
}else{
Node returnNode = MergeNode(nodeA.next,nodeB);
nodeA.next=returnNode;
return nodeA;
}
考虑以下链接列表以可视化此
2>4列表a
1>3列表b
几乎相同的答案（非递归）作为stefan，但几乎没有评论/有意义的变量名称。如果有人感兴趣
，则在评论中也涵盖了双重联系的清单考虑示例
5->10->15>21 // List1
2->3->6->20 //List2
Node MergeLists(List list1, List list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if(list1.head.data>list2.head.data){
listB =list2; // loop over this list as its head is smaller
listA =list1;
} else {
listA =list2; // loop over this list
listB =list1;
}
listB.currentNode=listB.head;
listA.currentNode=listA.head;
while(listB.currentNode!=null){
if(listB.currentNode.data<listA.currentNode.data){
Node insertFromNode = listB.currentNode.prev;
Node startingNode = listA.currentNode;
Node temp = inserFromNode.next;
inserFromNode.next = startingNode;
startingNode.next=temp;
startingNode.next.prev= startingNode; // for doubly linked list
startingNode.prev=inserFromNode; // for doubly linked list
listB.currentNode= listB.currentNode.next;
listA.currentNode= listA.currentNode.next;
}
else
{
listB.currentNode= listB.currentNode.next;
}
}
我的承担如下：
pseudocode：
Compare the two heads A and B.
If A <= B, then add A and move the head of A to the next node.
Similarly, if B < A, then add B and move the head of B to the next node B.
If both A and B are NULL then stop and return.
If either of them is NULL, then traverse the non null head till it becomes NULL.
代码：
public Node mergeLists(Node headA, Node headB) {
Node merge = null;
// If we have reached the end, then stop.
while (headA != null || headB != null) {
// if B is null then keep appending A, else check if value of A is lesser or equal than B
if (headB == null || (headA != null && headA.data <= headB.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headA.data);
// Since A is <= B, Move head of A to next node
headA = headA.next;
// if A is null then keep appending B, else check if value of B is lesser than A
} else if (headA == null || (headB != null && headB.data < headA.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headB.data);
// Since B is < A, Move head of B to next node
headB = headB.next;
}
}
return merge;
}
public Node add(Node head, int data) {
Node end = new Node(data);
if (head == null) {
return end;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = end;
return head;
}
/* Simple/Elegant Iterative approach in Java*/
private static LinkedList mergeLists(LinkedList list1, LinkedList list2) {
Node head1 = list1.start;
Node head2 = list2.start;
if (list1.size == 0)
return list2;
if (list2.size == 0)
return list1;
LinkedList mergeList = new LinkedList();
while (head1 != null && head2 != null) {
if (head1.getData() < head2.getData()) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
} else {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
}
while (head1 != null) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
}
while (head2 != null) {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
return mergeList;
}
/* Build-In singly LinkedList class in Java*/
class LinkedList {
Node start;
int size = 0;
void insert(int data) {
if (start == null)
start = new Node(data);
else {
Node temp = start;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(new Node(data));
}
size++;
}
@Override
public String toString() {
String str = "";
Node temp=start;
while (temp != null) {
str += temp.getData() + "-->";
temp = temp.getNext();
}
return str;
}
}
LLNode *mergeSorted(LLNode *h1, LLNode *h2)
{
LLNode *h3=NULL;
LLNode *h3l;
if(h1==NULL && h2==NULL)
return NULL;
if(h1==NULL)
return h2;
if(h2==NULL)
return h1;
if(h1->data<h2->data)
{
h3=h1;
h1=h1->next;
}
else
{
h3=h2;
h2=h2->next;
}
LLNode *oh=h3;
while(h1!=NULL && h2!=NULL)
{
if(h1->data<h2->data)
{
h3->next=h1;
h3=h3->next;
h1=h1->next;
}
else
{
h3->next=h2;
h3=h3->next;
h2=h2->next;
}
}
if(h1==NULL)
h3->next=h2;
if(h2==NULL)
h3->next=h1;
return oh;
}
// Common code for insert at the end
private void insertEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
newNode.next = head;
head = tail = newNode;
return;
}
Node tempNode = tail;
tempNode.next = newNode;
tail = newNode;
}
private void mergerTwoSortedListInAscOrder(Node tempNode1, Node tempNode2) {
if (tempNode1 == null && tempNode2 == null)
return;
if (tempNode1 == null) {
head3 = tempNode2;
return;
}
if (tempNode2 == null) {
head3 = tempNode1;
return;
}
while (tempNode1 != null && tempNode2 != null) {
if (tempNode1.mData < tempNode2.mData) {
insertEndForHead3(tempNode1.mData);
tempNode1 = tempNode1.next;
} else if (tempNode1.mData > tempNode2.mData) {
insertEndForHead3(tempNode2.mData);
tempNode2 = tempNode2.next;
} else {
insertEndForHead3(tempNode1.mData);
insertEndForHead3(tempNode2.mData);
tempNode1 = tempNode1.next;
tempNode2 = tempNode2.next;
}
}
if (tempNode1 != null) {
while (tempNode1 != null) {
insertEndForHead3(tempNode1.mData);
tempNode1 = tempNode1.next;
}
}
if (tempNode2 != null) {
while (tempNode2 != null) {
insertEndForHead3(tempNode2.mData);
tempNode2 = tempNode2.next;
}
}
}
:) glbmp
public static Node merge(Node h1, Node h2) {
Node h3 = new Node(0);
Node current = h3;
boolean isH1Left = false;
boolean isH2Left = false;
while (h1 != null || h2 != null) {
if (h1.data <= h2.data) {
current.next = h1;
h1 = h1.next;
} else {
current.next = h2;
h2 = h2.next;
}
current = current.next;
if (h2 == null && h1 != null) {
isH1Left = true;
break;
}
if (h1 == null && h2 != null) {
isH2Left = true;
break;
}
}
if (isH1Left) {
while (h1 != null) {
current.next = h1;
current = current.next;
h1 = h1.next;
}
}
if (isH2Left) {
while (h2 != null) {
current.next = h2;
current = current.next;
h2 = h2.next;
}
}
h3 = h3.next;
return h3;
}
我在开始时只创建了一个虚拟节点，以保存许多“如果'条件。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode list1Cursor = l1;
ListNode list2Cursor = l2;
ListNode currentNode = new ListNode(-1); // Dummy node
ListNode head = currentNode;
while (list1Cursor != null && list2Cursor != null)
{
if (list1Cursor.val < list2Cursor.val) {
currentNode.next = list1Cursor;
list1Cursor = list1Cursor.next;
currentNode = currentNode.next;
} else {
currentNode.next = list2Cursor;
list2Cursor = list2Cursor.next;
currentNode = currentNode.next;
}
}
// Complete the rest
while (list1Cursor != null) {
currentNode.next = list1Cursor;
currentNode = currentNode.next;
list1Cursor = list1Cursor.next;
}
while (list2Cursor != null) {
currentNode.next = list2Cursor;
currentNode = currentNode.next;
list2Cursor = list2Cursor.next;
}
return head.next;
}
private static Node mergeLists(Node L1, Node L2) {
Node P1 = L1.val < L2.val ? L1 : L2;
Node P2 = L1.val < L2.val ? L2 : L1;
Node BigListHead = P1;
Node tempNode = null;
while (P1 != null && P2 != null) {
if (P1.next != null && P1.next.val >P2.val) {
tempNode = P1.next;
P1.next = P2;
P1 = P2;
P2 = tempNode;
} else if(P1.next != null)
P1 = P1.next;
else {
P1.next = P2;
break;
}
}
return BigListHead;
}
void printLL(){
NodeLL cur = head;
if(cur.getNext() == null){
System.out.println("LL is emplty");
}else{
//System.out.println("printing Node");
while(cur.getNext() != null){
cur = cur.getNext();
System.out.print(cur.getData()+ " ");
}
}
System.out.println();
}
void mergeSortedList(NodeLL node1, NodeLL node2){
NodeLL cur1 = node1.getNext();
NodeLL cur2 = node2.getNext();
NodeLL cur = head;
if(cur1 == null){
cur = node2;
}
if(cur2 == null){
cur = node1;
}
while(cur1 != null && cur2 != null){
if(cur1.getData() <= cur2.getData()){
cur.setNext(cur1);
cur1 = cur1.getNext();
}
else{
cur.setNext(cur2);
cur2 = cur2.getNext();
}
cur = cur.getNext();
}
while(cur1 != null){
cur.setNext(cur1);
cur1 = cur1.getNext();
cur = cur.getNext();
}
while(cur2 != null){
cur.setNext(cur2);
cur2 = cur2.getNext();
cur = cur.getNext();
}
printLL();
}
以下是如何合并两个排序链接列表头和headb：
的代码：Node* MergeLists1(Node *headA, Node* headB)
{
Node *p = headA;
Node *q = headB;
Node *result = NULL;
Node *pp = NULL;
Node *qq = NULL;
Node *head = NULL;
int value1 = 0;
int value2 = 0;
if((headA == NULL) && (headB == NULL))
{
return NULL;
}
if(headA==NULL)
{
return headB;
}
else if(headB==NULL)
{
return headA;
}
else
{
while((p != NULL) || (q != NULL))
{
if((p != NULL) && (q != NULL))
{
int value1 = p->data;
int value2 = q->data;
if(value1 <= value2)
{
pp = p->next;
p->next = NULL;
if(result == NULL)
{
head = result = p;
}
else
{
result->next = p;
result = p;
}
p = pp;
}
else
{
qq = q->next;
q->next = NULL;
if(result == NULL)
{
head = result = q;
}
else
{
result->next = q;
result = q;
}
q = qq;
}
}
else
{
if(p != NULL)
{
pp = p->next;
p->next = NULL;
result->next = p;
result = p;
p = pp;
}
if(q != NULL)
{
qq = q->next;
q->next = NULL;
result->next = q;
result = q;
q = qq;
}
}
}
}
return head;
}
不隶属于 StackOverflow
