链表一些算法技巧&模版总结

可以使用哑结点的技巧

1）创建哑结点new ListNode(0)

2）遍历head，每次遍历，将哑结点的next先保存下来

3）将哑结点的next指向目前遍历到的head值的节点

4）再将这次遍历临时保存下来的哑结点的next节点，重新连接到哑结点的m.next.next = temp

5）直到head为null，遍历完成，m.next即为翻转后的链表

可以使用快慢指针的方法

1）双指针移动，初始都指向head

2）先将p1移动k位

3）然后才开始移动p2，同时继续移动p1

4）直到p1指向末尾，那么p2将会移动L-k个位置，那么p2此时指向为倒数第k个节点

student *add(student *head)

{

student *p=new student,*p1, *p2

cin>>p->num>>p->name>>p->eng>>p->math>>p->c

if (head == NULL) // 检查头指针是否为空, 是直接赋值

head = p

else// 否, 则遍历链表找到合适的位置插入新节点

{

p1 = head

while(p1!=NULL)

{

p2 = p1 // 保存当前节点

p1=p1->next // 进入下个节点

}

p1=p // 存储新节点

p2->next=p1 // 将新节点赋值到链尾

}

return head

}

---