剑指offer:17 合并两个排序的链表

剑指offer 面试题17:

“题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.7中的链表1和链表2，则合并之后的升序链表如链表3所示。链表结点定义如下：

typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *pNext;
}LNode, *LinkList;</span>
           

1  思路分析：

    题意分解：两个链表都是递增的，因此显然不用蛮力，只需要两个指针各自指向一个链表，从左往右，比较指针指向的元素大小，时间复杂度即为O(max(m, n))

2   形成大体思路：

     a  首先把整个链表2看成一个只有一个节点，插入到链表1中

     b  插入之后，再将链表2中第二个节点插入到链表1之中。

    递增的价值就在于：

         i  每次插入不需要从链表1表头开始遍历，而只需要在之前插入之后的位置继续遍历。

         ii  顺序选择链表2中的元素插入，而不需要找最小的。

3  关键步骤：

a 每次插入链表1中时，需要考虑插入点是否是第一个元素。

b 第一次插入之后需要设置pre指针。

代码如下：

LinkList q17_ver2(LinkList& L1, LinkList& L2) {
    if (nullptr == L1) {
        return L2;
    } else if (nullptr == L2){
        return L1;
    }
    
    LNode *p1 = L1;
    LNode *p2 = L2;
    LNode *pre1 = nullptr;  //pre1 和 p1在L1上移动
    LNode *post2 = nullptr; //post2 记住L2中当前节点的后一个节点
    
    while (p1 && p2) {
        while (p1 && p1->data <= p2->data) {
            pre1 = p1;
            p1 = p1->pNext;
        }
        
        //
        if (nullptr == p1) {
            pre1->pNext = p2;
        } else {
            post2 = p2->pNext;
            
            //插入时判断是否为第一个元素
            if (pre1 == nullptr) {
                p2->pNext = p1;
                pre1 = p2;
                L1 = pre1;
            } else {
                p2->pNext = p1;
                pre1->pNext = p2;
                
                //一定要设置pre1，保证pre1一直是p1的前一个元素
                pre1 = p2;
            }
            
            p2 = post2;
        }
    }
    
    return L1;
}
           

4 小结

      题意虽然简单，但分析的时候还是不够透彻，考虑了特殊情况但忽略了一般情况，才导致没有一次通过。 说明做题时还是没有彻底的分析清楚，而且编码时，不够严谨，容易出些小问题。 这些都是应该在日后的刷题过程中有待提高的地方。

做完之后，看书上给出的是递归代码，我想，一时半会儿，没想着用递归写。所以自己独立思考也能偶尔多学到一些方法。