链表面试题积累(反转合并链表)

链表面试题积累

输入一个带头结点的链表。反转链表并返回头节点

• 注意边界条件控制
• 编码之前注意分析需求的内容。不要边写边思考

      struct ListNode {

        int m_nKey;
        ListNode*m_pNext;
      };

     // 输入一个带头结点的链表。反转链表并返回头节点
     ListNode*reverseListNode(ListNode*pHeader){

      /**
       *  1. 边界条件控制
       *  
          2. 用一个指针记录当前节点，然后分别2个指针记录前后节点
       */
     if (pHeader == nullptr) {
        return nullptr;
      }
      ListNode*pReverseNode = nullptr;
      ListNode*pNode = pHeader;
      ListNode*pPreNode = nullptr;

      while (pNode != nullptr) {
   
       ListNode*pNext = pNode->m_pNext;
       if (pNext == nullptr) {
           pReverseNode = pNode;
       }
       pNode->m_pNext = pPreNode;
       pPreNode = pNode;
       pNode = pNext;
     }
       return pReverseNode;
    }

// 2个有序的链表合并 然后生成一个新的有序的链表

• 如果有一个链表为空则返回另外一个链表
• 如果两个链表均为空则返回空
• 比较两个链表的头节点。拿比较小的ListNode当做大链表中下一个节点。

      ListNode*merge(ListNode*pHeader1,ListNode*pHeader2){
     // 边界条件思考。如果pHeader1为空或者pHeader2为空
       if (pHeader1 == nullptr) {
          return pHeader2;
       }else if(pHeader2 == nullptr){
          return pHeader1;
       }
       ListNode*mergeNode = nullptr;
       if  (pHeader1->m_nKey<pHeader2->m_nKey) {
       
         mergeNode = pHeader1;
         
         mergeNode->m_pNext = merge(pHeader1->m_pNext, pHeader2);
         
       }else{
       
        mergeNode = pHeader2;
        mergeNode->m_pNext = merge(pHeader1, pHeader2->m_pNext);
       }
       return mergeNode;
      }