【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;
}