- 在有關(guān)鏈表的題目中，最需要注意的地方就是各個(gè)結(jié)點(diǎn)引用的調(diào)整，否則很容易因?yàn)榛靵y的指向?qū)е滤姥h(huán)等情況。
- 技巧：定義引用指向（保存）某個(gè)結(jié)點(diǎn)暇仲，防止由于調(diào)整鏈表結(jié)構(gòu)，導(dǎo)致某些結(jié)點(diǎn)丟失副渴。
- 對(duì)于翻轉(zhuǎn)單鏈表一般有兩種做法：
- 1奈附、逐個(gè)翻轉(zhuǎn)，保存當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)煮剧，然后調(diào)整指向斥滤。
- 2讼载、不斷的將后面的鏈表丟到頭節(jié)點(diǎn)的后面，然后將頭節(jié)點(diǎn)丟到最后面中跌。
方法一：
/**
* 方法一：逐個(gè)翻轉(zhuǎn)
* @param head
* @return
*/
public static ListNode reverse(ListNode head) {
if (head == null)
return null;
ListNode pre = null;
ListNode cur = head;
while (cur != null)
{
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
方法二：
//方法二：不斷選擇后一個(gè)結(jié)點(diǎn)，插入到頭節(jié)點(diǎn)后面
public static ListNode re(ListNode head) {
if (head == null) return null;
if (head.next == null)
return head;
if (head.next.next == null){
ListNode n = head.next;
head.next = null;
n.next = head;
return n;
}
ListNode cur = head.next.next;
ListNode pre = head.next;
while (cur != null){
//臨時(shí)結(jié)點(diǎn)菇篡，存放當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
ListNode temp = cur.next;
//將cur的前一個(gè)結(jié)點(diǎn)指向cur的下一個(gè)結(jié)點(diǎn)
pre.next = temp;
//解除cur.next的先前指向漩符，重定向?yàn)閔ead下一個(gè)結(jié)點(diǎn)。
cur.next = head.next;
//解除head的先前指向驱还，重定向?yàn)閏ur
head.next = cur;
//調(diào)整引用嗜暴，cur向后一位
cur = temp;
}
//添加引用到頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，即翻轉(zhuǎn)鏈表后的新頭結(jié)點(diǎn)议蟆。
ListNode newNode = head.next;
//移動(dòng)頭節(jié)點(diǎn)到尾部
pre.next = head;
//解除下一個(gè)指向的引用闷沥，避免死循環(huán)
head.next = null;
return newNode;
}
https://github.com/yuanoOo/Algorithm/tree/master/Linked%20List
