Springboot java开发环境变量 ASP.NET DHCP triggers pagination smtp Way.js History.js vue路由 vue响应式布局 jq获取元素宽度 软件测试项目实战案例 js获取数组第一个元素 base64转16进制 html好看的字体 eclipse显示左边目录 python正则 python抛出异常 python等待10秒 python程序代码 python调用命令行 java方法重载 java学习平台 java中float java的输入 计算机电子书 火牛软件 音频频谱分析软件 robotstudio win10有几个版本 古风头像女动漫 vue引入第三方js 正则表达式数字 qq黑客软件 bin文件编辑器 allowtransparency 迅雷单机游戏下载 混凝土配合比计算软件 pyodbc
当前位置: 首页 > 学习教程  > 编程语言

单向链表的反转的三种方式

2021/1/28 23:29:23 文章标签:

单向链表的反转的三种方式 单链表的反转有三种实现方法 遍历法(结构清晰易懂,时间复杂度低)递归法(代码简洁,但时间复杂度高,尤其是在链表长度超过12000之后)内置类法(代码简洁&am…

单向链表的反转的三种方式

单链表的反转有三种实现方法

  • 遍历法(结构清晰易懂,时间复杂度低)
  • 递归法(代码简洁,但时间复杂度高,尤其是在链表长度超过12000之后)
  • 内置类法(代码简洁,使用内置LinkedList类)

1.遍历法(关键代码)

    static Node reverse(Node head) {
    	if(head == null){
    		return null;
    	}
        Node pre = null;
        Node cur = head;
        Node reHead = null;
        
        //如果当前结点为空,结束循环
        while (cur != null) {
        	//保存下一个结点,以免丢失
            Node temp = cur.next;
            //1.对pre和cur结点的关系进行反转。本来是pre指向cur的,用下面这条代码能够把cur指向pre。
            cur.next = pre;
            
            //2.如果下一个结点为空,那他就是反转链表的头结点
            if (temp == null) {
                reHead = cur;
            }
            
            //3.上一个结点已经反转完成啦!现在要移动到下一个结点了!
            pre = cur;
            cur = temp;
        }
        return reHead;
    }

上面方式的化简版,代码简短,但是没那么容易理解

static Node reverse(Node head) {
	Node pre = null;
	Node temp = null;

	while(head != null){
		//1.记录下一个结点
		//2.指针反转
		temp = head.next;
		head.next = pre;

		//3.光标移向原链表的下一个结点
		pre = head;
		head = temp;
	}

	return pre;
}


2.递归法(关键代码)

static Node reverse(Node head) {
    //我们从原链表的头结点开始
    Node cur = head;
    //递归到原链表的尾结点结束。递归到了尾结点的时候,就返回当前结点。
    if (cur == null || cur.next == null) {
        return cur;
    } else {
        Node reHead = reverse(cur.next);
        cur.next.next = cur;
        cur.next = null;
        return reHead;
    }
}

3.内置类法

LinkedList没有提供反转链表的相关函数,以下是通过foreach实现链表反转
static LinkedList reverse(LinkedList linkedList) {
    LinkedList<Object> newLinkedList = new LinkedList<>();
    for (Object object : linkedList) {
        newLinkedList.add(0, object);
    }
    return newLinkedList;
}

转自:https://blog.csdn.net/baidu_34122324/article/details/82850861


本文链接: http://www.dtmao.cc/news_show_650216.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?