单链表面试题

1.合并两个有序链表

1. 链表的分割
   我们的思路可能是先定义两个结构体指针n1和n2存放head的值,然后遍历链表,将节点指向的值小于X的链表放在b1当中,然后将节点指向的值小于X的节点放在n2当中,最后再将两个链表链接起来就可以了.但是当我们正在去实现代码的时候会发现,我们这样在原先链表上做这些操作很复杂,既要考虑节点的指向问题又要重新定义一个prev节点来记录前一个节点的位置.所以这种方法我们先放在一边看看有没有简单一点的方法.我们顺着刚才的思维再往下想,我们是不是可以重新定义两个结构体变量,为这个变量开辟一块和原先结构体占用空间大小一样的空间.然后我们不在原先的链表上操作而是在这两个新定义的"链表"中操作,这样就避免了在原先的链表上操作了.
2. 链表的回文结构
   把两个链表变成一样的顺序了.这种方法按照逻辑是没有错的,但是我们说,这个题有没有优解,我们可以想到前一章我们讲过链表的中间节点和链表反转链表,我们仔细一想其实会发现这种头插尾插的形式还是比较麻烦的,我们可以利用前面的结论先找到链表的中间节点,再将中间节点后面的链表进行反转,这样也能得到我们想要的结果.