题目:

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的

解答:

#import "NSListNode.h"
#import <Foundation/Foundation.h>

// 解法二: 排序 (递归)
NSListNode * recursionMergeNewListNode (NSListNode *firstListNode, NSListNode *secondListNode) {
    if (firstListNode == nil && secondListNode == nil) {
        return nil;
    }
    
    if (firstListNode == nil) {
        return secondListNode;
    }
    
    if (secondListNode == nil) {
        return firstListNode;
    }

    NSListNode *tmpListNode = firstListNode;
    
    if ([tmpListNode.value integerValue] < [secondListNode.value integerValue]) {
        tmpListNode.next = recursionMergeNewListNode(firstListNode.next, secondListNode);
    }
    else {
        tmpListNode = secondListNode;
        tmpListNode.next = recursionMergeNewListNode(firstListNode, secondListNode.next);
    }
    
    return tmpListNode;
}


// 解法一: 排序 (循环)
NSListNode * mergeNewListNode (NSListNode *firstListNode, NSListNode *secondListNode) {
    if (firstListNode == nil && secondListNode == nil) {
        return nil;
    }
    
    if (firstListNode == nil) {
        return secondListNode;
    }
    
    if (secondListNode == nil) {
        return firstListNode;
    }
    
    NSListNode *rootListNode = [[NSListNode alloc] init];
    NSListNode *tmpListNode = rootListNode;
    
    while (firstListNode != nil && secondListNode != nil) {
        if ([firstListNode.value integerValue] < [secondListNode.value integerValue]) {
            tmpListNode.next = firstListNode;
            firstListNode = firstListNode.next;
        }
        else {
            tmpListNode.next = secondListNode;
            secondListNode = secondListNode.next;
        }
        tmpListNode = tmpListNode.next;
    }
    
    if (firstListNode != nil) {
        tmpListNode.next = firstListNode;
    }
    
    if (secondListNode != nil) {
        tmpListNode.next = secondListNode;
    }
    
    return rootListNode.next;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSListNode  *firstListNote = [[NSListNode alloc] init];
        firstListNote.value =  @"1";
        firstListNote.next = [[NSListNode alloc] init];
        firstListNote.next.value = @"3";
        firstListNote.next.next = [[NSListNode alloc] init];
        firstListNote.next.next.value = @"5";
        firstListNote.next.next.next = nil;
        
        NSListNode  *secondListNote = [[NSListNode alloc] init];
        secondListNote.value =  @"2";
        secondListNote.next = [[NSListNode alloc] init];
        secondListNote.next.value = @"4";
        secondListNote.next.next = [[NSListNode alloc] init];
        secondListNote.next.next.value = @"6";
        secondListNote.next.next.next = nil;
        
       NSListNode *mergeListNode = recursionMergeNewListNode(firstListNote, secondListNote);
        
        while (mergeListNode != nil) {
            NSLog(@"%@", mergeListNode.value);
            mergeListNode = mergeListNode.next;
        }

    }
    return 0;
}