链表算法-回文结构、两个链表公共节点

最近一直在刷算法，以前没有重视这块，偶然巧合下，想到了某几次的面试，虽然没有以这个为主，但是也都有问过算法的题，因为没有这方面的积累，所以心底里一直抗拒，最近也有时间，觉得还是要花时间学习研究算法的东西，锻炼锻炼逻辑思路和解决思路。

学习路程肯定是要把基础掌握好的，你得知道各个名词的含义，如链表是什么，单链表怎么实现，双链表怎么实现，你才能处理把握链表出的方向的算法题，如树，什么是二叉树，二叉搜索树，二三树，红黑树，你知道每个结构的定义以及特性，才能掌握和思考怎么处理，这一定是必然的。

今天弄几个链表算法

1.判断链表回文结构

1.对单链表逆顺序是否与原链表顺序相同，也就是回文链表，如1->2 ->1，那么1->2->1这个就是true，如1->2，那么逆序就是2->1那么就是false；

因为链表有个特点不知道长度，不能随机用下标访问数据，所以需要遍历到最后才能全部知道数据，这道题可以采用先遍历将链表数据存储到数组中，然后采用二分法进行前后对比数据，直到遇到不相等则直接退出循环，返回false，一直相等则就是链表的回文数据，

public boolean isPail (ListNode head) {List<Integer> list = new ArrayList();ListNode w = head;// 将链表数据存储到数组中while (w != null) {list.add(w.val);w = w.next;}int size = list.size();boolean result = true;// 将数组长度/2 得到回文顺序交界点for (int i = 0; i < size / 2; i++) {// 从前往后对比直到交界点，全部都比对完毕if (list.get(i).equals(list.get(size - i - 1))) {} else {result = false;break;}}return result;
}// 节点，是个内部类
public static class ListNode {int val;ListNode next = null;
}

测试示例

 ListNode ListNode = new ListNode();ListNode.val = 1;ListNode.next = null;ListNode ListNodeNext = new ListNode();ListNodeNext.val = 2;ListNodeNext.next = null;ListNode.next = ListNodeNext;ListNode ListNodeNextn = new ListNode();ListNodeNextn.val = 3;ListNodeNextn.next = null;ListNodeNext.next = ListNodeNextn;ListNode ListNodeNextns = new ListNode();ListNodeNextns.val = 3;ListNodeNextns.next = null;ListNodeNextn.next = ListNodeNextns;ListNode ListNodeNextnn = new ListNode();ListNodeNextnn.val = 2;ListNodeNextnn.next = null;ListNodeNextns.next = ListNodeNextnn;ListNode ListNodeNextnns = new ListNode();ListNodeNextnns.val = 1;ListNodeNextnns.next = null;ListNodeNextnn.next = ListNodeNextnns;System.out.println(AboutLinked.isPail2(ListNode));

输入：1->2->3->3-2>1返回结果 true

自己写的一个版本，当时主要考虑不想遍历放入数组中，再次进行遍历，所以用了String的字符串拼接方式。

public boolean isPail (ListNode head) {String s="";String ss ="";ListNode w = head;while (w != null) {s+=w.val+"";ss=w.val+ss;;w = w.next;}return s.equals(ss);}

这种方式答案是对的，但是性能太差，输入量特多的情况下，会超时反馈不出结果，我想主要原因还是出在了字符串拼接导致的问题，我本想减少代码，减少一些遍历，但是却出现了其他的性能问题，不用StringBuffer的原因是想要倒着拼接，如果使用reverse则负数又会出现问题，

String采用连接运算符(+)效率低下，都是上述循环、大批量数据情况造成的，每做一次"+"就产生个StringBuilder对象，然后append后就扔掉。下次循环再到达时重新产生个StringBuilder对象，然后append字符串，如此循环直至结束。如果我们直接采用StringBuilder对象进行append的话，我们可以节省创建和销毁对象的时间。

2. NC66两个链表的第一个公共节点

输入两个非公共的链表{1,2,3}以及{4,5}和一个公共链表{6,7}，塞入到两个公共链表里头，变为{1,2,3,6,7}以及{4,5,6,7}，请输出他们的第一个公共节点，那么得到的就是{6,7}

我们需要两个链表一一比对，直到某个链表为空，另一个链表还有值时进行两个链表替换，然后继续对比，本示例当对比空以后将temp赋值为temp2{1,2,3,6,7}，temp2赋值为temp则{4,5,6,7}，当temp链表走到空时，temp2链表已经赋值为1，那么当temp为空时，就赋值temp2为4，此时temp就为2，就变成了2:4，3:5，6:6 相同直接结束循环，是不是清楚很多，那么代码如下

public class Solution {public static class ListNode {int val;ListNode next = null;}
// pHead1={1,2,3,6,7}  pHead2={4,5,6,7}public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode temp = pHead1;ListNode temp1 = pHead2;while (temp != temp1) {// 如果为空互相替换来找出公共节点temp = temp!=null?temp.next:pHead2;temp1 = temp1!=null?temp1.next:pHead1;}return temp;}}

咱们就不演示测试了否择还得遍历打印链表，本次案例结果返回6->7