鏈表操作是數(shù)據(jù)結構里面最基礎的了，我們都記得數(shù)據(jù)結構書上那個箭頭指來指去的圖暴构，但其實我當時考研的時候也沒有對鏈表從內(nèi)存的角度有一個深刻的認識跪呈，所以我對鏈表操作一直挺頭大的，雖然鏈表只是一種極端的二叉樹丹壕，但我甚至覺得二叉樹比鏈表好操作多了庆械。
眾所周知，鏈表的操作里經(jīng)常要用到fakeHead這么一個頭結點菌赖，作用是一番操作之后缭乘，可以用fakeHead.next用來返回修改后的鏈表。但我有時候疑惑，這個fakeHead會指向改變后的鏈表嗎堕绩。策幼。
比如下面的操作是經(jīng)常會做的：
ListNode fakeHead = new ListNode(-1);
//停留在原點指路
fakeHead.next = head;
//鐵頭娃，去遍歷鏈表
ListNode curNode = fakeHead;
其實仔細想想奴紧，從STACK和HEAP的角度想特姐，保存在HEAP中的fakeHead與curNode(fakeHead對象的引用)都指向了同一塊內(nèi)存，那么鐵頭娃curNode去改變了鏈表(head開頭)的結構之后黍氮，fakeHead只要知道那塊內(nèi)存的起始地址(fakeHead.next)就行了唐含，這個地址有可能改變(比如第一個結點被刪除了)也沒有關系。
下面是我頭腦清醒的狀態(tài)下快速寫出的一個刪除指定value的結點的一個demo沫浆，指針指來指去的那部分最好自己紙上畫畫捷枯，直接看可能比較繞：
/**
* 刪除node.val 為targetVal的node
* Created by DrunkPiano on 28/11/2017.
*/
public class DeleteNode {
private ListNode deleteNode(int targetVal, ListNode head) {
if (head == null) {
return null;
}
//先用一個fakeHead保存一下head的位置
ListNode fakeHead = new ListNode(-1);
fakeHead.next = head;
ListNode curNode = fakeHead;
ListNode nextNode = curNode.next;
while (curNode != null && nextNode != null) {
if (nextNode.val == targetVal) {
curNode.next = nextNode.next;
}
curNode = curNode.next;
//判空
if (curNode != null) {
nextNode = nextNode.next;
}
}
return fakeHead.next;
}
public static void main(String[] args) {
int[] nodes = {1, 2, 3, 1, 5};
ListNode fakeHead = new ListNode(-1);
ListNode head = fakeHead;
for (Integer i : nodes) {
head.next = new ListNode(i);
head = head.next;
}
//這里傳入fakeHead.next
ListNode resNode = new DeleteNode().deleteNode(5, fakeHead.next);
while (resNode != null) {
System.out.println(resNode.val + ", ");
resNode = resNode.next;
}
}
}
至于劍指offer之類書上的在O(1)時間刪除節(jié)點，其實是知道targetNode的地址的情況专执。
反轉(zhuǎn)單鏈表
這是個很好的問題淮捆，可以看你對鏈表操作熟悉不熟悉，follow up可以看你對迭代和遞歸是不是熟悉本股。
簡單寫一下迭代和遞歸兩種方法：
Iterative：
類似維護一個prev, cur, next的窗口：
public class MyClass {
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
ListNode result = new MyClass().reverseList(head);
while(result != null){
System.out.println(result.val);
result = result.next;
}
}
ListNode reverseList(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode prev = null, cur = head, next = null;
while(cur != null){
//保存next
next = cur.next;
//改變指向
cur.next = prev;
//窗口右移
prev = cur;
cur = next;
}
return prev;
}
}
class ListNode{
ListNode(int value){
val = value;
}
int val;
ListNode next;
}
recursion:
如果后面還有node攀痊，就遞歸調(diào)用自己來處理后面的node；本質(zhì)上是從倒數(shù)第二個結點開始依次向前改變指向拄显。遞歸的思維難度還是比較難的苟径，尤其是head.next = null;這句不寫的話會產(chǎn)生循環(huán)鏈表導致陷入無限遞歸哦。
public class MyClass {
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
ListNode result = new MyClass().reverseList(head);
while(result != null){
System.out.println(result.val);
result = result.next;
}
}
ListNode reverseList(ListNode head){
if(head == null || head.next == null)
return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
class ListNode{
ListNode(int value){
val = value;
}
int val;
ListNode next;
}
ref:
http://blog.csdn.net/lavor_zl/article/details/42803431
http://blog.csdn.net/yuxin6866/article/details/52132229
反轉(zhuǎn)單鏈表：
https://www.youtube.com/watch?v=XwIivDg1BlY
