反转链表的几种方法以及链表合并
反转链表
http://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca
提目地址: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; }