图解单链表逆序

简介: 逆序思想代码测试本篇博客,比较简单。对单链表逆序不理解的看看就可以了。逆序思想现假设有一链表,有待逆序操作。我们首先想到的就是将那个指针关系逆序了就行了呗。

本篇博客,比较简单。对单链表逆序不理解的看看就可以了。


逆序思想

现假设有一链表,有待逆序操作。我们首先想到的就是将那个指针关系逆序了就行了呗。

事实上,就是这样。博主就是以这个为目标来完成的单链表逆序操作。

Node pre = null;
Node post = null;

while(head!=null){
  post = head.next;
  head.next = pre;
  pre = head;
  head = post;
}

这便是逆序的核心了。下面我们就来一步步的讲解。

  • 首次逆序:
    一开始的话,pre,post都设置为null。这是必须的,因为在head.next=pre这行代码执行完成后,我们原始的那个head节点的next将变成null,也就是我们整个链表的null了。

    想象一下,原来的那个链表的最后面的next不也是一个null吗?这里道理是一致的。

此时,更新pre为原来的head节点,也是为了下一步的逆序做准备,而head也自然的变成了原来的head.next了。

  • 不断逆序。
    单链表逆序

抱歉,手抖了一下,画错了。大家见谅。手绘图上的第五次示意pre节点应该在节点5的位置,没有了head

从图例中我们也不难看出,我们就是一次次的将head向后移,同时更新pre节点,来达到逆序的效果。

代码

/**
 * @Date 2016年9月9日
 *
 * @author 郭  璞
 *
 */
package list;

/**
 * @author 郭 璞
 * 
 *         <br>
 *         逆置单链表
 *
 */
public class ReverseList {

    public static void main(String[] args) {

        Node head = new Node(1);
        int[] value = {2,3,4,5};
        Node temp = head;
        for(int i = 0 ; i< value.length;i++) {
            Node node = new Node(value[i]);
            temp.next = node;
            temp = temp.next;
        }
        printList(head);
        // 反序输出一个单链表
        head = reverse(head);
        printList(head);

        // 再次反向
        head = reverseSingleList(head);
        printList(head);
    }


    public static void printList(Node head) {
        while(head!=null) {
            System.out.print("\t"+head.value);
            head = head.next;
        }
        System.out.println();
    }

    public static Node reverse(Node head) {
        Node pre = null;
        Node post = null;

        while(head!=null) {
            post = head.next;
            head.next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }


    public static Node reverseSingleList(Node head) {
        Node pre = null;
        Node next = null;

        while(head!=null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }



}

class Node {
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}

测试

经测试,代码输出正确。

    1   2   3   4   5
    5   4   3   2   1
    1   2   3   4   5
目录
相关文章
|
27天前
|
存储
链表题目练习及讲解(下)
链表题目练习及讲解(下)
24 9
|
27天前
链表题目练习及讲解(上)
链表题目练习及讲解(上)
23 1
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
|
5月前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
33 0
|
6月前
|
算法
LeetCode刷题---160. 相交链表(双指针-对撞指针)
LeetCode刷题---160. 相交链表(双指针-对撞指针)
|
6月前
|
算法 索引
LeetCode刷题---141. 环形链表(双指针-快慢指针)
LeetCode刷题---141. 环形链表(双指针-快慢指针)
|
6月前
|
算法 索引
LeetCode刷题---142. 环形链表 II(双指针-快慢指针)
LeetCode刷题---142. 环形链表 II(双指针-快慢指针)
|
C语言
【每日易题】数据结构链表篇——单链表oj题(1),几道典型例题带你快速掌握单链表
【每日易题】数据结构链表篇——单链表oj题(1),几道典型例题带你快速掌握单链表
80 0
|
存储
图解LeetCode——234. 回文链表
图解LeetCode——234. 回文链表
111 1
力扣82删除排序链表中的重复元素 II:思路分析+代码实现+方法总结(三指针法&快慢指针法【双指针】&递归法)
力扣82删除排序链表中的重复元素 II:思路分析+代码实现+方法总结(三指针法&快慢指针法【双指针】&递归法)
68 0