链表
链表的问题，大部分从头指针开始，必要时需要新建一个头结点。
结束条件也多为当前结点为空，或者下一个结点为空。
1.链表反转
非递归方式，操作顺序：
- 计算n指针，确定下个结点的位置
- 放心断链，指针反转，c指向p
- 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
