在第一篇文章中为了说明递归如何写，所以对于链表的操作都是用递归来写的，我们发现递归写起来比较简洁，但是执行的过程有点复杂，并且往往在实际的算法中都是要将递归改成循环来做，可以一定程度上减少开销提高性能。下面我们来看看循环如何实现的。

链表的反转

需要验证准确性的话，可以去leetcode上去做这道题，题号为206.这道题还是比较经典的。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        ListNode currentNode = head;
        while(currentNode != null){
            ListNode next = currentNode.next;
            currentNode.next = newHead;
            newHead = currentNode;
            currentNode = next;
        }
        return newHead;
    }
}

一开始学的时候看的答案就是这个方法，显然是要比递归好的，但是如果不理解的话，光靠背很容易出错，并且也不大背的上，如今重温这道题，其实是很简单的，我们下面用图示来阐述。

主要的思想是用两个指针，其中newHead指向的是反转成功的链表的头部，currentHead指向的是还没有反转的链表的头部：

image

初始状态是newHead指向null，currentHead指向的是第一个元素，一直往后遍历直到newHead指向最后一个元素为止：

image

下面展示的是其中某个时间点的指向细节：

image

理解了上面的图示，程序就呼之欲出了。

删除链表节点

题目为：给一个数值，找到链表中这个等于这个数的所有节点并且删除。效果如下，比如给的数是2，则表示删除链表中所有为2的节点。

image

这个题目也是非常地经典，面试中经常会看到。我们务必要掌握。

这个其实有两种解题思路，比较简单的是增加一个虚拟的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //构造一个虚拟的头节点，指向head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        //用一个指针指向虚拟头节点，因为虚拟头节点还要表示去重后的链表的头节点
        ListNode curr = dummy;
        //进入循环，看虚拟头节点下一个节点
        while(curr.next != null){
            //如果下一个节点不为空并且值是等于val的，那么就说明要删除掉这个节点
            //所谓的删除，只是改变指针，使得这个要删除的节点没有任何引用即可，java会自动回收它
            if(curr.next.val == val){
                ListNode delNode = curr.next;
                curr.next = delNode.next;
            }else{
                //说明值不等于val，那么就后移一个即可
                curr = curr.next;
            }
        }
        //返回头节点
        return dummy.next;
    }
}

这种实现的方式相对来说比较简单。大体的解决思路为：

image

另一种是比较特殊的处理方式，不需要虚拟的头节点就可以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //对于比较特殊的，就是head也与val相等的情况，需要出一下
        while(head != null && head.val == val){
            head = head.next;
        }
        //走到这，还需要判断一下head是否为null，因为有可能这个链表全部都等于val
        //那么经过上一步之后这个链表已经为null了，那么就不需要进入下一步了
        if(head == null){
            return null;
        }
        //此时链表开头的重复元素全部剔除了，下面就是普通的后续的元素，循环判断删除即可
        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next;
            }else{
                prev = prev.next;
            }
        }
        return head;
    }
}

没错，代码大体是相似的，特殊的处理在于一开始的节点的值与val相等的处理，所以我们需要先处理一下head以及head的后面连续的都是等于val的节点，直到处理到不为val的节点为止，即把开头相等的节点全部剔除掉，下面再继续循环判断是否相等。

关于链表的题目还有很多，由于链表数据结构比较简单，但是算法并不简单，所以面试中经常会被问道，需要好好准备一下。后面会进行相应的总结。