一、虚拟头节点的选取

一般来说，如果对链表进行的操作有可能改变head节点，比如删除head或者移动head，可以对边界条件进行判空。但这种情况的一般做法是：我们创建一个虚拟头节点，无论head如何变化，虚拟头节点是始终存在的。

虚拟头节点的运用十分广泛，我们来看一看具体的运用。

19. 删除链表的倒数第N个节点

题目描述

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思考

一般来说，单链表的删除操作，需要知道该节点的pre，让pre.next = pre.next.next。

• 可能会删除头部，可以使用虚拟头节点化解。
• 双指针，快指针先走n步，慢指针先不动。
• 两者同时向后走，当快指针指向最后一个节点，慢指针正好走到倒数第N+1个节点。
• 删除慢指针的下一个节点：slow.next = slow.next.next;。

虚拟头节点

头节点head将会发生变化的时候，头节点将会派上用场。

一、普通创建一个节点即可。ListNode dummy = new ListNode(-1);

二、注意让虚拟头节点和真实头节点产生联系。dummy.next = head;

三、最后返回的值是虚拟头节点的next，因为头节点可能存在被删除的情况：return dummy.next;

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;		//虚拟节点和head联系起来
        ListNode slow = dummy, fast = dummy; //快慢指针同时指向虚拟头
        while( n-- > 0){
            fast = fast.next; //快指针先走n步
        }
        while(fast.next != null){ //同时向后移动
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next; //删除目标节点
        return dummy.next;       //返回dummy.next
    }
}

二、使用双指针找到指定位置的节点

同样的，双指针的做法通常在链表题中也比较常见，可以经常看到有快慢指针解决寻找位置为k的节点【比如上面那题】，判断链表成环等问题。除了快慢指针，可能还有每次列出一对节点，进行交换或者其他操作，也是巧妙利用了指针。

61. 选转链表

61. 旋转链表

难度中等328

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思考：

• k%链表长度
• 双指针找到倒数第k+1的位置。
• 最后一个节点指向第一个节点，倒数第k+1个节点指向null，head指向倒数第k个点。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        int n = 0;
        for(ListNode p = head; p != null; p = p.next) n++; //链表总结点数
        k %= n; //每次要移动尾部的k个数到头部
        ListNode slow = head, fast = head;
        while(k -- > 0) fast = fast.next; 
        while(fast.next!= null){
            fast = fast.next;
            slow = slow.next;
        }//双指针找到倒数第k+1的位置
        fast.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }
}

24. 两两交换链表中的节点

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        for(ListNode p = dummy; p.next != null && p.next.next != null;){
            ListNode a = p.next,b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dummy.next;
    }
}

三、反转链表的相关问题

206. 反转链表

题目描述

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

迭代做法

我们的目标就是：让最开始的节点指向空，第二个节点指向第一个节点……最后一个节点指向倒数第二个节点，最后返回最后一个节点。

如何实现呢，其实思路很简单：

• 我们需要每次用两个指针拿出两个两个节点【当然最开始的两个节点我们把它看成null和1】，我们用pre表示第一个节点，用curr表示第二个节点，翻转 关系表示为：curr.next = pre；
• 我们每次将指针同时向后移动，表示处理下一对节点，pre向后移动表示为：pre = curr，但curr怎么向后移呢，此时curr的next指针已经指向pre，也就是说第一步的时候，curr的next指针已经丢失，这样是显然不行的。
• 这时，我们就需要用到链表中一个非常常用的手段，将curr.next指针暂存起来，ListNode next = curr.next，curr向后移动就可以表示为：curr = next；
• 终止条件是什么呢，其实链表的题目画一画图基本就出来了，当curr指向null的时候，pre正好指向最后一个节点，也就是本题需要的新头，返回pre即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, curr = head, next = null;
        while( curr!=null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;

        }
        return pre;
    }
}

【第二个迭代做法】

思路大致差不多，不解释了，直接画图。

    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode p = head, q = p.next;
        while(q!=null){
            ListNode n = q.next;
            q.next = p;
            p = q;
            q = n;
        }
        head.next = null;
        return p;
    }

92. 反转链表 II

题目描述

92. 反转链表 II

该题解参考自Acwing yxc：https://www.acwing.com/solution/content/174/

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思考

1. 特判：如果m == n，表示无需反转，直接return head即可。

2. 这个反转过程中，头节点可能会被改变，我们使用虚拟头节点化解即可。

3. 反转的过程如何？

   • 确定我们需要的节点位置

     • 设反转段为[b,d]，反转段的迁移节点为a，反转段的后一节点为c。
     • a就是从虚拟节点走m-1步的位置，d就是从虚拟节点走n步的位置。
     • 那么相应的，b = a.next; c = d.next。

   • 反转[b,d]，如何实现呢？这个问题转化为将head为b的链表，以d为结尾的链表的反转问题，参考之前的做法，我们可以如下做：

     • 双指针每次取出两个节点，p和q，p = b，q = p.next。
     • 使用临时节点o存储q的下一个位置，保存一下。o = q.next;
     • 让q的next指向p。q.next = p;
     • p和q同时向后移。p = q; q = o;
     • 终止条件在于：q这个节点是不是已经到头了，是不是走到了c的位置。

   • 此时链表其实已经被分为三段，我们需要拼接这三段就可以。

     • b.next = c;
     • a.next = d;

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy, d = dummy;
        for(int i = 0; i < m - 1; i++) a = a.next;
        for(int i = 0; i < n ; i ++) d = d.next;

        ListNode b = a.next;
        ListNode c = d.next;

        for(ListNode p = b, q = p.next; q!=c;){
            ListNode o = q.next;
            q.next = p;
            p = q;
            q = o;
        }
        b.next = c;
        a.next = d;
        return dummy.next;
    }
}

链表中元素的删除操作

237. 删除链表中的节点

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

• 链表至少包含两个节点。
• 链表中所有节点的值都是唯一的。
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
• 不要从你的函数中返回任何结果。

思考：

• 将要删除的节点伪装成下一个节点，然后将下一个节点删除：
  • 值变成下一个节点的值。
  • next指向下一个节点的next。

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

83. 删除排序链表中的重复元素

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

思考：

• 加入链表本身为空，返回，做一个特判。
• 假设保留第一个节点，让curr指向head。
• 判断下一个节点的取值和curr取值的关系：
  • 如果相等，就删除下一个节点，即curr.next = curr.next.next
  • 如果不相等，则让curr向后移一位，即curr = curr.next
• 终止条件是curr.next==null。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode curr = head;
        while(curr.next !=null){
            if(curr.next.val == curr.val){
                curr.next = curr.next.next;
            }else{
                curr = curr.next;
            }
        }
        return head;
    }
}

【链表专题】刷题心得

原文：https://www.cnblogs.com/summerday152/p/13620339.html