学习数据结构（6）单链表OJ上

1.移除链表元素

解法一：（我的做法）在遍历的同时移除，代码写法比较复杂

解法二：创建新的链表，遍历原链表，将非val的节点尾插到新链表，注意，如果原链表结尾是val节点需要将新链表的尾节点的next置为NULL；

我的写法：

参考写法：（更简洁的写法）

2.反转链表

解法一：（我的思路）

将前三个节点地址分别储存在head，secondnode，thirdnode中，当thirdnode不为NULL时，对链表遍历，每次遍历将secondnode指向head，再将head，secondnode，thirdnode分别向后移动一个节点，最后返回secondnode，并将原链表头节点的指向改为NULL

解法二：创建一个新链表，遍历原链表，将节点依次头插到新链表中

解法三：（参考代码）和解法一类似，但对起始的三个相邻节点的选择不同，且更加简洁

 或  

3.链表的中间节点

解法一：（我的解法）遍历链表，得到节点个数，节点个数除以二，得到从头节点到中间节点的遍历次数，再遍历链表，找到中间节点，但较复杂

解法二：（快慢指针）创建两个指针，遍历链表，快指针每次移动两个节点，慢指针每次移动一个节点，由于节点个数分奇偶，所以分两种情况（如下图），pfast->next为NULL或pfast为NULL即为终点，此时pslow所在节点即为中间节点，这种算法效率更高，也容易实现，代码简洁

我的写法：

参考代码（更加简洁）：

4.合并两个有序链表

解法一：创建新的空链表，在两个指针都不为NULL的条件下，两个指针分别同时遍历两个链表，每次遍历比较节点中数据的大小，小的数据节点尾插到新链表中，退出循环后，将不为空的链表指针以后的所有节点尾插到新链表中，但这种方法由于新链表为空链表，在插入第一个节点时与插入后面的节点写法不同，造成代码比较冗杂

解法二：创建非空链表，节点尾插到非空链表上，最后释放申请的空间