剑指Offer面试题16反转链表(递归和非递归)，面试题17合并两个排序的链表(递归)

面试题16：反转链表（递归和非递归）

输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思路1：定义三个指针，分别是当前要反转的结点，它的前一个结点和后一个结点。

思路2：用递归。先找到倒数后两个结点反转，依次向前。

以下是本题Java实现：

class ListNode{ int value; ListNode next; public ListNode(int x) { value = x; } } public class ReverseList { private ListNode reverseList(ListNode headNode){ if(headNode == null){ System.out.println("输入头结点为空"); return null; } ListNode nowNode = headNode;//当前要反转的结点 ListNode preNode = null;//前一个结点 ListNode nextNode = null;//后一个结点 ListNode revHead = null;//反转后的头结点 while(nowNode != null){ if(nowNode.next == null){//反转后的头结点是之前的尾结点 revHead = nowNode; } nextNode = nowNode.next; nowNode.next = preNode; preNode = nowNode; nowNode = nextNode; } return revHead; } private void print(ListNode headNode){ if(headNode == null){ System.out.println("输入头结点为空"); return; } while(headNode != null){ System.out.println(headNode.value); headNode = headNode.next; } } //递归方法(不太好理解) private ListNode digui(ListNode headNode){ //判断链表为空或者链表中只有一个元素 if(headNode == null || headNode.next == null){ return headNode; }else{ ListNode revHead = digui(headNode.next);//先反转后面的链表 headNode.next.next = headNode;//反转 headNode.next = null; return revHead; } } public static void main(String[] args) { ListNode one = new ListNode(1); ListNode two = new ListNode(2); ListNode three = new ListNode(3); one.next = two; two.next = three; ReverseList test = new ReverseList(); System.out.println("反转前:"); test.print(one); System.out.println("反转后:"); //test.print(test.reverseList(one)); test.print(test.digui(one)); } }

面试题17：合并两个排序的链表(递归)

输入两个递增的链表，合并这两个链表并使新链表仍然是递增的。

思路：递归。每次比较两个链表的第一个结点，提出小的，然后它的next等于递归返回值。

本题Java实现如下：

public class Merge { private ListNode merge(ListNode L1,ListNode L2){ if(L1 == null){ return L2; }else if(L2 == null){ return L1; } ListNode mergeHead = null; if(L1.value < L2.value){ mergeHead = L1; mergeHead.next = merge(L1.next, L2); }else{ mergeHead = L2; mergeHead.next = merge(L1, L2.next); } return mergeHead; } //尾插法建立链表 private ListNode create(int[] arr){ if(arr.length == 0){ System.out.println("输入数组为空"); return null; } ListNode headNode = new ListNode(arr[0]); ListNode p = headNode; for(int i= 1;i<arr.length;i++){ ListNode node = new ListNode(arr[i]); p.next = node; p = p.next; } return headNode; } //打印输出 private void print(ListNode headNode){ if(headNode == null){ System.out.println("打印时输入为空"); return; } while(headNode != null){ System.out.println(headNode.value); headNode = headNode.next; } } public static void main(String[] args) { int[] a = {1,3,5,7}; int[] b = {2,4,6,8}; Merge test = new Merge(); ListNode A = test.create(a); ListNode B = test.create(b); System.out.println("A: "); test.print(A); System.out.println("B: "); test.print(B); System.out.println("Merge: "); test.print(test.merge(A, B)); } } class ListNode{ int value; ListNode next; public ListNode(int x) { value = x; } }