个人博客首发：https://wubobo952.github.io/
如何快速写出正确的链表代码
技巧一：理解指针或引用的含义
指针也可以理解为“引用”。
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
技巧二：警惕指针丢失和内存泄漏
插入，删除时需警惕
反例：这样就让原本 p 指向的下一个结点断开了,这样操作会导致 x 后面的结点都被截断了
//x 是要插入的结点，p 的下一个结点指向 x
p->next=x
//新插入的结点 x 的下一个结点指向 x 自己，从而导致之后的结点全部丢失了
x.next=p->next
正确的：就是换一下位置
p->next=x.next
p->next=x
技巧三：利用哨兵简化实现难度
哨兵结点的链表叫带头链表，其实就是为了解决边界的问题的,带头链表的头部是没有数据的，只有下一个节点的索引。
因为某些情况下同样的操作例如添加，删除，处理是不同的。
添加的结点是不是头结点
//不是，如上面的添加一样
p->next=NewNode.next
p->next=NewNode
//是
if(p==null){
p=NewNode
}
删除 p 指针的后结点，删除的结点是不是最后一个结点
//不是,只要把 p 指针的下一个结点,指向 p 的下下一个结点即可
p.next=p.next.next
//是
if（p.next==null）{
p=null;
}
这就是如果没有用带头的链表在处理插入或者删除时的边界情况，需要不同的逻辑去处理，很容易写漏
如果我们引入哨兵结点，在任何时候，不管链表是不是空，p 指针都会一直指向这个哨兵结点,因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码
技巧四：重点留意边界条件处理
- 链表为空时，代码是否能正常工作
- 链表只包含一个结点的时候,或者只包含两个结点的时候，代码能否正常的工作
- 代码在处理头节点和尾结点的时候能否正常的工作
技巧五：举例画图，辅助思考
做题时候最好还是要画图，毕竟单纯靠想很容易混乱。
技巧六：多写多练，没有捷径
常见的链表操作
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除表倒数第n个结点
- 求链表的中间结点
leetcode对应：206，141，21，19，876
单链表反转：https://leetcode-cn.com/problems/reverse-linked-list/
反转单链的时候需要注意这个单链表是否是有带头节点的
- 无->原地反转
- 有->带头节点的反转（插入法） 从第二个结点开始插入，把遍历到的结点插入到头结点的后面，直到遍历结束
//无带头节点反转
public static ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
//带头结点的
public static ListNode reverseListHead(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next ;
ListNode cur = head.next;
head.next = null;
while (cur != null) {
next = cur.next;
cur.next = head.next;
head.next = cur;
cur = next;
}
return head;
}
链表中环的检测：https://leetcode-cn.com/problems/linked-list-cycle/
public static boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode p = head;
ListNode q = head;
while (q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
if (q == p) {
return true;
}
}
return false;
}
合并两个有序的链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return null;
}
ListNode newNode = new ListNode();
ListNode newNodeHead = newNode;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
newNodeHead.next = l1;
l1 = l1.next;
} else {
newNodeHead.next = l2;
l2 = l2.next;
}
newNodeHead = newNodeHead.next;
}
newNodeHead.next = l1 == null ? l2 : l1;
return newNode.next;
}
删除表倒数第n个结点：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode newNode = new ListNode();
newNode.next = head;
ListNode q = newNode;
ListNode p = newNode;
for (int i = 1; i <= n+1; i++) {
q = q.next;
}
while (q != null) {
q = q.next;
p = p.next;
}
p.next = p.next.next;
return newNode.next;
}
求链表的中间结点：https://leetcode-cn.com/problems/middle-of-the-linked-list/
public static ListNode middleNode(ListNode head) {
ListNode q = head;
ListNode p = head;
while (q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
System.out.println(p.val);
System.out.println(q.val);
if (q.next!=null){
return p.next;
}
return p;
}
实现的思路都有写在练习demo里面，练习测试的地址：https://github.com/wubobo952/LeetCode
