反转链表的几种方法以及链表合并

提目地址：https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=190&tags=&title=&diffculty=0&judgeStatus=0&rp=1
两个链表相加成链表，这个题目需要借助于栈结构，剩下的一个就是链表的合并和反转，这里涉及到了链表的反转方法，在这里一起总结下，首先这个是合并相加链表的代码

    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 涉及到链表的反转
       Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode p1 = head1;
        ListNode p2 = head2;
        while (p1 != null) {
            stack1.add(p1.val);
            p1 = p1.next;
        }
        while (p2 != null) {
            stack2.add(p2.val);
            p2 = p2.next;
        }
        ListNode head = new ListNode(-1);
        int temp = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || temp!=0) {
            int num1 = stack1.isEmpty() ? 0 : stack1.pop();
            int num2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = (num1+num2+temp)%10;
            temp = (num1+num2+temp)/10;
            ListNode next = head.next;
            ListNode node = new ListNode(sum);
            head.next = node;
            node.next = next;
        }
        return head.next;
    }

然后重点是总结反转链表的方法
1.题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null;
2.知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。
3.这就需要把结点挨个从链表上摘下来，做调整；
4.这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针p记录后一个结点地址，避免结点丢失。
5.例子：
以head结点为例步骤如下：
   1.反转后head是指向null，所以未反转的时候其前一个结点应该是null，初始化pre指针为null；
   2.用p指针记录head的下一个结点head.next；
   3.从链表上摘下head，即让head.next指向pre；
   4.此时已完成head结点的摘取及与前一个节点的连接，则我们需要操作下一个结点：故需移动pre和head，让pre指向head，head指向下一个节点。
重复这四个操作直到head走完原链表，指向null时，循环结束，返回pre。
思路说到这里，通过图像可能理解更加深刻，这是三指针法的图示：

//方法一两个辅助指针
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //初始化pre指针，用于记录当前结点的前一个结点地址
        ListNode pre = null;
        //初始化p指针，用于记录当前结点的下一个结点地址
        ListNode p = null;
        //head指向null时，循环终止。
        while(head != null){
            //先用p指针记录当前结点的下一个结点地址。
            p = head.next;
            //让被当前结点与链表断开并指向前一个结点pre。
            head.next = pre;
            //pre指针指向当前结点
            pre = head;
            //head指向p(保存着原链表中head的下一个结点地址)
            head = p;
        }
        return pre;//当循环结束时,pre所指的就是反转链表的头结点
    }
}
//方法二头插入法
 public ListNode ReverseList(ListNode head) {
          ListNode newHead=null;
          ListNode currentNode = head;
          if(head==null || head.next==null){
              return head;
          }
         while(currentNode !=null){
             ListNode next = currentNode.next;
             currentNode.next=newHead;  
             newHead = currentNode;
             currentNode=next;
         }
        return newHead;
    }