【OJ】单链表刷题

1. 反转链表（206）

1.1 题目描述

1.2 题目分析

1.2.1 头插法

要将原来的链表进行反转，很容易想到，将原来的节点取下来，然后一个一个进行头插到新链表中struct ListNode* newhead=NULL。
原链表中，如果cur不为空，那么cur->next=newhead,再将newhead置为新链表的头节点。
为了方便记录原链表节点的位置，在原链表上定义一个struct ListNode* next=cur->next。

如果cur为空，这里就需要一个新的链表，所以最后不要忘记返回新链表的头节点。

1.2.2 箭头反转

还有一种方法就是将这些节点的箭头反向，也就是将后一个节点的next等于前一个节点。

反转之后就是这样:

也就是说：先定义两个指针，先将n1置为空，然后n2指向头节点，再将n2->next=n1。然后继续往后走，需要记录n2后一个节点位置，再定义一个n3=head->next,只要链表不为空，就让 n2->next=n1;n1=n2;n2=n3。
但是在最后一步n3可能为空，所以得加一个判断，为空就不往后执行了。
最值得注意的一点是，如果原链表为空，那么后面都不执行，所以开始得加一个判断

    if(head==NULL){return NULL;}

1.3 题目代码

1.3.1 头插入

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

1.3.2 箭头反转

struct ListNode* reverseList(struct ListNode* head){if(head==NULL){return NULL;}struct ListNode* n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}

2.合并两个有序链表（21）

2.1 题目描述

2.2 题目分析

题目要求是按照升序返回合并的原来排好序的两个链表，这里就可以用尾插，比较两个链表节点的val，对比一下，取小的进行尾插。

这里肯定要事先判断一下这两个链表是不是为空：如果链表1为空，就直接返回链表2。同样，链表2为空，就返回链表1。

      if(list1==NULL){return list2;}if(list2==NULL){return list1;}

在已有的链表上面经行插入比较繁琐，就直接用一个新的，最后返回排好链表的头节点就行。
只有两个链表都不为空时，再考虑是链表1节点的val与链表2的val：如果 list1->val< list2->val，还是得判断一下这个新链表里面有没有节点：没有就直接让head=tail=list1，有就实现尾插。

           if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}

然后链表1继续往后走。
但是如果 list1->val< list2->val是错误的，那么链表2也是同样的：

           if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;

当一个链表已经排好了，如果剩下的是链表1，就直接插入

       if(list1){tail->next=list1;}

如果剩下的是链表2，就直接插入：

       if(list2){tail->next=list2;}

最后别忘记返回头节点。

2.3 题目代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* head=NULL;struct ListNode* tail=NULL;while(list1&&list2){if(list1->val<list2->val){if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(tail==NULL){head=tail=list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}return head;}