單列表反轉兩種方式（第一種按照c語言實現，第二種方式java語言實現）

單鏈表的反轉是常見的面試題目。本文總結了2種方法。

1 定義

單鏈表node的數據結構定義如下：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

方法1：就地反轉法

思路

把當前鏈表的下一個節點pCur插入到頭結點dummy的下一個節點中，就地反轉。

dummy->1->2->3->4->5的就地反轉過程：

dummy->2->1->3->4->5
dummy->3->2->1->4->5
dummy->4>-3->2->1->5
dummy->5->4->3->2->1

解釋

1初始狀態

過程

pCur是需要反轉的節點。

prev連線下一次需要反轉的節點
反轉節點pCur
糾正頭結點dummy的指向
pCur指向下一次要反轉的節點
虛擬碼

1 prev.next = pCur.next;
2 pCur.next = dummy.next;
3 dummy.next = pCur;
4 pCur = prev.next;

回圈條件

pCur is not null

程式碼

// 1.就地反轉法
    public ListNode reverseList1(ListNode head) {
        if (head == null)
            return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy.next;
        ListNode pCur = prev.next;
        while (pCur != null) {
            prev.next = pCur.next;
            pCur.next = dummy.next;
            dummy.next = pCur;
            pCur = prev.next;
        }
        return dummy.next;
    }

總結

1個頭結點，2個指針，4行程式碼
注意初始狀態和結束狀態，體會中間的圖解過程。

方法2：新建鏈表，頭節點插入法

3.1 思路
新建一個頭結點，遍歷原鏈表，把每個節點用頭結點插入到新建鏈表中。最後，新建的鏈表就是反轉後的鏈表。

解釋

1 初始狀態

過程

pCur是要插入到新鏈表的節點。

pNex是臨時儲存的pCur的next。

pNex儲存下一次要插入的節點
把pCur插入到dummy中
糾正頭結點dummy的指向
pCur指向下一次要插入的節點

虛擬碼

1 pNex = pCur.next
2 pCur.next = dummy.next
3 dummy.next = pCur
4 pCur = pNex  

回圈條件

pCur is not null

具體程式碼：

// 2.新建鏈表,頭節點插入法
   //列表反轉
    public void reverse (Hero5 head)
    {
    	if (head.next==null||head.next.next==null) {//如果列表爲空或者只有一個節點則無需反轉
			return ;
		}
    	Hero5 cur = head.next;//當前節點
    	Hero5 nex =null;//備用節點，用來存放cur的下一個節點
    	Hero5 temp =new Hero5(0,"","");//建立一個空列表
    	while (cur!=null) {
			nex = cur.next;//定義nex指針使得cur移動
			cur.next = temp.next;//cur後一個指針始終在新列表頂端
			temp.next = cur;//每次將nex指針頂下去
			cur = nex;	//原來列表依次移動	
		}
    	head.next = temp.next;//原來列表頭指針指向新列表頭
    }

總結

1個頭結點，2個指針（包含一個臨時儲存節點的pNex），4行程式碼
注意初始狀態和結束狀態，體會中間的圖解過程。