Reverse Second half of LinkedList Java实现

第三道Amazon面试coding题练习。

这道题是说，有一个linkedlist  {1,2,3,4,5,6,7,8}转换为{1,2,3,4,8,7,6,5}，初看不难，其实也不难。LinkedList 非常好理解，就是多一个指针。

翻转一串LinkedList的示例网上大把，随便看看就好。

package quinn;import quinn.List.ListNode;public class ReverseLinkedList {public static void main(String[] args) {// TODO Auto-generated method stubint[] list = {1,2,3,4,5,6,7,8,9};/////创建linkedList//ListNode head = new ListNode(list[0]);ListNode node = head;for(int i=1; i < list.length; i++){ListNode NewNode = new ListNode(list[i]); node.next = NewNode;node = NewNode;}int length = getLength(head);//假装不知道长度是多少，没有看到具体的题，就让我随便写写吧head = ReverseHalf(length,head);//先取一半，再翻转OutPutList(head);}private static ListNode ReverseHalf(int length, ListNode head) {// TODO Auto-generated method stubListNode first = head;ListNode halfhead;if(length<4)//特殊情况，如果小于4了，完全没有必要翻转return head;else{int halflen = (int) Math.ceil((double)length/2);//没看具体题目，假定9/2的时候是5System.out.println("一半的长度是:\t"+halflen);for(int i=0; i < halflen-1;i++)//这里减一是为了让指针停留在前一半最后一个节点上{head = head.next;}halfhead = RecursiveReverse(head.next);//翻转后一半head.next = halfhead;//前一半连接上翻转后的后一半}return first;}private static int getLength(ListNode head) {// TODO Auto-generated method stubint size = 0;while(head!= null){size++;head = head.next;}return size;}private static ListNode RecursiveReverse(ListNode head) {//递归的进行反转，递归的比较好理解if(head==null || head.next==null){return head;}ListNode second = head.next;head.next = null;ListNode rest = RecursiveReverse(second);second.next = head;return rest;}private static ListNode reverseList(ListNode head) {// TODO Auto-generated method stubif(head==null||head.next==null)return head;ListNode p1 = head;ListNode p2 =head.next;head.next = null;while(p1!=null && p2!=null){ListNode t = p2.next;p2.next = p1;p1 = p2;if(t!=null){p2 = t;}elsebreak;}return p2;}private static void OutPutList(ListNode head) {// TODO Auto-generated method stubwhile(head!=null){System.out.println(head.val);head =head.next;}}}

package quinn;public class List {public static class ListNode{int val;ListNode next;public ListNode(int val){this.val = val;this.next = null;}}}