JZ3 从尾到头打印链表
（简单）
题目
描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
0 <= 链表长度 <= 1000
示例1
输入：
{1,2,3}
返回值：
[3,2,1]
示例2
输入：
{67,0,24,58}
返回值：
[58,24,0,67]
思路
在做这道题时，我想到了两种方法。
(先吐槽一点，题目中说了输入的是链表的头结点，但是我在刷题平台上测试，发现其实输入的是第一个有效结点才对）
【方法一】：首先看到打印逆序链表，那么便可以借助栈这种数据结构，将链表结点顺序加入到栈中，那么再将出栈结果加入到结果链表中，那么自然就得到了逆序的链表，具体实现如下：
【实现】
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
public class JZ3从尾到头打印链表 {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
//listNode = listNode.next;
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (stack.size() > 0) {
list.add(stack.pop());
}
return list;
}
}
【方法二】：因为返回结果为一个 ArrayList 对象，因此我们便可利用此集合类所实现的方法来进行逆序链表的生成，即遍历参数链表，按顺序取出其中结点，每次都用 ArrayList 的 add 函数将此结点插入到首位，那么最终便可得到参数链表的逆序形式，具体实现如下：
【实现】
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
public class JZ3从尾到头打印链表 {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
while (listNode != null) {
list.add(0, listNode.val);
listNode = listNode.next;
}
return list;
}
}
JZ36 两个链表的第一个公共结点
（简单）
题目
描述
输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
示例1
输入：
{1,2,3},{4,5},{6,7}
返回值：
{6,7}
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入：
{1},{2,3},{}
返回值：
{}
说明：
2个链表没有公共节点 ,返回null，后台打印{}
思路
当拿到这道题时，我是没看明白那两个示例是什么意思，如果能给一个图的话就很好理解题意了（题解中的图就十分形象地解释了示例），但是想要做出来仍然需要很巧妙的方法。这里我就不再自己总结了，官方给出的题解十分的详细和通俗，此方法十分巧妙，虽然简单但是不容易想到（有多少人能轻易想到这题能和加法交换律的思想联系起来呢），而且对于临界情况也同样可以处理，此方法被命名为双指针法：
下面给出 Java 代码的实现：
【实现】
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class JZ36两个链表的第一个公共结点 {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode ta = pHead1, tb = pHead2;
while (ta != tb) {
tb = tb != null ? tb.next : pHead1;
ta = ta != null ? ta.next : pHead2;
}
return ta;
}
}
