当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

两种方法反转单链表

发表于: 2012-12-17   作者:128kj   来源:转载   浏览:
摘要: /** * @author luochengcheng * 定义一个单链表 */ class Node { //变量 private int record; //指向下一个对象 private Node nextNode; public Node(int record) {
/**  
 * @author luochengcheng  
 * 定义一个单链表  
 */  
class Node {   
    //变量   
    private int record;   
    //指向下一个对象   
    private Node nextNode;   
  
    public Node(int record) {   
        super();   
        this.record = record;   
    }   
    public int getRecord() {   
        return record;   
    }   
    public void setRecord(int record) {   
        this.record = record;   
    }   
    public Node getNextNode() {   
        return nextNode;   
    }   
    public void setNextNode(Node nextNode) {   
        this.nextNode = nextNode;   
    }   
}   
  
/**  
 * @author luochengcheng  
 *  两种方式实现单链表的反转(递归、普通)  
 *  新手强烈建议旁边拿着纸和笔跟着代码画图(便于理解)  
 */  
public class ReverseSingleList {   
    /**   
     * 递归,在反转当前节点之前先反转后续节点   
     */  
    public static Node reverse(Node head) {   
        if (null == head || null == head.getNextNode()) {   
            return head;   
        }   
        Node reversedHead = reverse(head.getNextNode());   
        head.getNextNode().setNextNode(head);   
        head.setNextNode(null);   
        return reversedHead;   
    }   
  
    /**   
     * 遍历,将当前节点的下一个节点缓存后更改当前节点指针   
     *    
     */  
    public static Node reverse2(Node head) {   
        if (null == head) {   
            return head;   
        }   
        Node pre = head;   
        Node cur = head.getNextNode();   
        Node next;   
        while (null != cur) {   
            next = cur.getNextNode();   
            cur.setNextNode(pre);   
            pre = cur;   
            cur = next;   
        }   
        //将原链表的头节点的下一个节点置为null,再将反转后的头节点赋给head      
        head.setNextNode(null);   
        head = pre;   
           
        return head;   
    }   
  
    public static void main(String[] args) {   
        Node head = new Node(0);   
        Node tmp = null;   
        Node cur = null;   
        // 构造一个长度为10的链表,保存头节点对象head      
        for (int i = 1; i < 10; i++) {   
            tmp = new Node(i);   
            if (1 == i) {   
                head.setNextNode(tmp);   
            } else {   
                cur.setNextNode(tmp);   
            }   
            cur = tmp;   
        }   
        //打印反转前的链表   
        Node h = head;   
        while (null != h) {   
            System.out.print(h.getRecord() + " ");   
            h = h.getNextNode();   
        }   
        //调用反转方法   
        head = reverse2(head);   
        System.out.println("\n**************************");   
        //打印反转后的结果   
        while (null != head) {   
            System.out.print(head.getRecord() + " ");   
            head = head.getNextNode();   
        }   
    }   
}  


代码来自: http://poly.iteye.com/blog/1748272

运行:
C:\ex>java   ReverseSingleList
0 1 2 3 4 5 6 7 8 9
**************************
9 8 7 6 5 4 3 2 1 0
源码:

两种方法反转单链表

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
这几天找工作,遇到一个挺好玩的笔试题,做完之后想了一个比较简单的实现方法。 题目是:实现一个单
这几天找工作,遇到一个挺好玩的笔试题,做完之后想了一个比较简单的实现方法。 题目是:实现一个单
简介 这是一个相对比较简单直接的问题。假设我们有这么一个单链表,需要将它反转过来。对它分析的过
算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了。尤其对于
单链表反转:这个是反转是要破坏原有数据结构的。 算法1:红色线为将要修改节点的指向,这里只要关
1 递归,很简单 代码: #include<iostream> using namespace std; typedef struct node{ int
单链表的反转是常见的面试题目。本文总结了2种方法。 1 定义 单链表node的数据结构定义如下: class
单链表反转 指针坑 当我看到单链表反转这题目时,感觉这么简单啊。事实很多坑,一不小心就跳进去了
单链表反转的分析及实现 我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素
[转]单链表反转问题 原文: http://nkshili.spaces.live.com/blog/cns!BB418D20B454CBE7!1489.entry
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号