链表操作是数据结构里面最基础的了，我们都记得数据结构书上那个箭头指来指去的图，但其实我当时考研的时候也没有对链表从内存的角度有一个深刻的认识，所以我对链表操作一直挺头大的，虽然链表只是一种极端的二叉树，但我甚至觉得二叉树比链表好操作多了。
众所周知，链表的操作里经常要用到fakeHead这么一个头结点，作用是一番操作之后，可以用fakeHead.next用来返回修改后的链表。但我有时候疑惑，这个fakeHead会指向改变后的链表吗。。
比如下面的操作是经常会做的：
ListNode fakeHead = new ListNode(-1);
//停留在原点指路
fakeHead.next = head;
//铁头娃，去遍历链表
ListNode curNode = fakeHead;
其实仔细想想，从STACK和HEAP的角度想，保存在HEAP中的fakeHead与curNode(fakeHead对象的引用)都指向了同一块内存，那么铁头娃curNode去改变了链表(head开头)的结构之后，fakeHead只要知道那块内存的起始地址(fakeHead.next)就行了，这个地址有可能改变(比如第一个结点被删除了)也没有关系。
下面是我头脑清醒的状态下快速写出的一个删除指定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)时间删除节点，其实是知道targetNode的地址的情况。
反转单链表
这是个很好的问题，可以看你对链表操作熟悉不熟悉，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，就递归调用自己来处理后面的node；本质上是从倒数第二个结点开始依次向前改变指向。递归的思维难度还是比较难的，尤其是head.next = null;这句不写的话会产生循环链表导致陷入无限递归哦。
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
反转单链表：
https://www.youtube.com/watch?v=XwIivDg1BlY
网友评论