【剑指offer】反转链表并返回链表的头指针

前提：

Node定义和链表的定义，参见文章Java 单链表操作

【解题思路】：

三个指针 ：pBefore pCurrent（即将改变next方向的指针）,pNext 三个指针 

public Node inverseLinkList(Node pHead) { // TODO Auto-generated method stub Node inverseNode=null; Node pCurrent=pHead; Node pBefore=null; Node pNext=null; if(pCurrent==null||pCurrent.next==null) return pHead;//验证链表只有一个节点和链表为空 while(pCurrent!=null){ pNext=pCurrent.next; if(pNext==null) inverseNode=pCurrent; pCurrent.next=pBefore; pBefore=pCurrent; pCurrent=pNext; } //改变链表的首尾指针， tail=head; head=inverseNode; //改变链表的首尾的值 return inverseNode; } }

方法二：迭代方法：

</pre><pre name="code" class="java">public Node inverseLinkList_Recursively(Node pNode){ //Node pNode=pHead; Node pBefore=null; Node pNext=null; Node reverseNode=null; if(pNode==null) return pNode; if(pNode.next!=null) { pNext=pNode.next; if(pNext==null) reverseNode=pNode; pBefore=inverseLinkList_Recursively(pNode); pNode.next=pBefore; pBefore=pNode; pNode=pNext; } return reverseNode; }

测试代码：

MyLinkList linklist3=new MyLinkList(); linklist3.addFirst(3); linklist3.add(2, 4); linklist3.add(3, 5); linklist3.add(3, 6); linklist3.print(linklist3.head); Node newHead=linklist3.inverseLinkList(linklist3.head); //改变linklist3.head处值为null 测试空指针 linklist3.print(newHead);运行结果：

the elements in the list : 3 4 5 6 the elements in the list : 6 5 4 3