链表

链表的问题，大部分从头指针开始，必要时需要新建一个头结点。

结束条件也多为当前结点为空，或者下一个结点为空。

1.链表反转

非递归方式，操作顺序：

1. 计算n指针，确定下个结点的位置
2. 放心断链，指针反转，c指向p
3. p、c指针前移，为下一次操作做准备

/*
 * struct ListNode {
      int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* reverseList(ListNode* head) {
    ListNode *c = head;
    ListNode *p = NULL;
    ListNode *n = NULL;
    while(c != NULL){
        n = c->next;    //防止丢失链表
        c->next = p;    //断链

        p = c;          //向前移动
        c = n;
    }
    return p;
}

图解.png

递归：

ListNode* Tback(ListNode* A)
{
    if(A->next == NULL )
    {
        return A;
    }
    else 
    {
        ListNode* newhead = Tback(A->next);     
        A->next->next = A;      //A的下一个结点指向A
        A->next = NULL;         //A下一个结点的地址为NULL
        return newhead;
    }
}
ListNode* reverseList(ListNode* head) {
    if(head == NULL)
        return head;
    else
    {
        head = Tback(head); 
        return head;
    }
}

图解.png

2.合并两个排序的链表

用递归！！别装逼，装逼容易翻车，链表这种东西，越少代码量越不容易错。

要注意的是，在递归算法中，需要将你最后要保留的变量，return出来。

 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 {
     if(pHead1 == NULL)
         return pHead2;
     else if(pHead2 == NULL)
         return pHead1;

     ListNode* myList = NULL;
     if(pHead1->val < pHead2->val){
         myList = pHead1;
         myList->next = Merge(pHead1->next, pHead2);
     }
     else {
         myList = pHead2;
         myList->next = Merge(pHead1, pHead2->next);
     }
     return myList;
 }

合并链表.png