劍指offer面試題24:反轉連結清單

題目：定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。連結清單定義如下:

class ListNode{

int value;

ListNode next;

 ListNode(int value){

 this.value = value;

 }

}

直接上代碼：

public class sortArrayByOddEven {
	public static void main(String[] args) {

		ListNode pHead = new ListNode(1);
		ListNode pAhead = new ListNode(3);
		ListNode pBhead = new ListNode(5);
		ListNode pChead = new ListNode(7);
		pHead.next = pAhead;
		pAhead.next = pBhead;
		pBhead.next = pChead;
		pHead = reversalNode(pHead);
		while (pHead != null) {
			System.out.print(pHead.value + ",");
			pHead = pHead.next;
		}

	}

	private static ListNode reversalNode(ListNode pHead) {
		if(pHead==null) 
			return null;
		
		ListNode pNode = pHead;
		ListNode next = null;    
		ListNode pre = null;
		ListNode reservalNode = null;
		while(pNode!=null) {
			next = pNode.next;
			if(next == null) {
				return reservalNode;   //當next==null時，Pnode則為我們需要傳回當節點
			}
			pNode.next=pre;   //pre每次儲存上一個節點，将本節點.next 指派為上一個節點
			pre = pNode;     //将本節點作為複制為pre 作為下一個節點當上節點。
			pNode = next;//進行下一次循環
		}
		return reservalNode;
	}
           

分析：這個是根據老師當代碼改寫成當java代碼；

1）在分析後我們其實可以發現，在while循環中當if()判斷句其實可以不要，我們優化代碼

private static ListNode reversalNode(ListNode pHead) {
		if(pHead==null) 
			return null;
		
		ListNode pNode = pHead;
		ListNode next = null;    
		ListNode pre = null;
		while(pNode!=null) {
			next = pNode.next;	
			pNode.next=pre;   //pre每次儲存上一個節點，将本節點.next 指派為上一個節點
			pre = pNode;     //将本節點作為複制為pre 作為下一個節點當上節點。
			pNode = next;//進行下一次循環
		}
		return pre;
	}
           

這樣是因為我們當pNode.next不存在時，我們儲存當pre就是我們要傳回當頭節點，是以直接傳回即可，不用再進行判斷。