反转链表：非递归实现

Java

解题思路

反转链表首先得有三个指针分别指向上一个，当前和下一个，上一个用于标记新链表，当前用于反转，下一个用于标记旧链表，当前反转之后，新旧链表改动，则新链表头指向新链表头cur，cur指向下一个要处理的节点，即next，next指向下一个要处理的节点的下一个，否则修改下一个节点后就丢失了旧链表。大致示意图如下：

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 三个节点的引用
        ListNode pre,cur,next;

        // 初始化引用，这里next要保证cur不为空才有，所以稍后处理
        cur = head;
        pre = null;

        // 直到没有要被处理的节点
        while (cur != null){
            // next引用，确保找得到旧链表
            next = cur.next;

            // 修改当前节点的next引用，引用到前面的元素
            cur.next = pre;

            // 经过上一步操作后，pre指向新的头节点
            pre = cur;
            // 指向下一个要处理的元素
            cur = next;
        }

        // 返回新链表的头结点
        return pre;
    }
}

【数据结构与算法】反转链表：非递归实现