首页 > 编程语言 > 详细

让我们来写个算法吧,(1)翻转单链表

时间:2020-02-09 23:36:22      阅读:111      评论:0      收藏:0      [点我收藏+]

作为面试中最最最常考的链表题之一,翻转单链表。有以下两种解法:

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

  Node类定义如下

class Node {

    int value;

    Node next;

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

 

 

1.遍历法

  此方法根据链表遍历,通过拆分,刷新节点来达到翻转单链表的功能。

  

  草稿过程 

    第一次遍历 主链表 2->3->4   输出链表 1

    第二次遍历 主链表3->4         输出链表 2->1  

    第三次遍历 主链表 4        输出链表 3->2->1

    第四次遍历 主链表           输出链表 4->3->2->1

  分析过程完了,我们上代码咯:

  

public static Node reverseNode(Node node) {
   // 因为node节点会发生变化,所以用于存储node节点    
  Node tmp = null;
Node result =null;

  while(node!=null){
    // 先存起来
    node.next = tmp;
    
    node.next = result;

    result = node;
    
    //上面两步是为了保存每次的断开节点,第一次遍历,result =null; 1.next =null; result =1 ;
    //第二次遍历,result =1; 2.next =1; result =2->1 ;
    node = tmp;
  } return result; }

 

2.递归法 

  主要是通过程序栈保留的案发现场进行节点的断开和重组

  

  

    public static Node reverseNode(Node node) {
        
        if(node==null || node.next == null) {
            return node;
        }
        //案发现场
        Node temp = node.next;
        Node returnNode = reverseNode(node.next);
        // 从当前节点断开
        node.next = null;
        // 用案发现场的节点指向当前节点
        temp.next = node;
        
        return returnNode;

    }

 

让我们来写个算法吧,(1)翻转单链表

原文:https://www.cnblogs.com/leaveast/p/12289328.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!