精华内容
下载资源
问答
  • Java单向链表反转

    2021-09-01 14:09:59
    单向链表反转就是将链表的指针方向改变。由于单链表没有指向前一个结点的指针,所以,我们定义一个指向前一个节点的指针pre,用于存储每一个节点的前一个结点;定义一个保存当前节点的指针cur以及下一个节点指针的...

    要求

    给出单链表的头节点 head ,要求反转链表,并返回反转后的链表。

    实现原理

    单向链表反转就是将链表的指针方向改变。由于单链表没有指向前一个结点的指针,所以,我们定义一个指向前一个节点的指针pre,用于存储每一个节点的前一个结点;定义一个保存当前节点的指针cur以及下一个节点指针的next。定义好之后,遍历单链表,将next指向cur的下一个节点,将cur的next指向pre(此时链表是断开状态),pre向后移动,cur向后移动,直至遍历到最后一个结点为止。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    代码实现

    
    public class LinkedList {
        public static Node reverse(Node head){
            //如果链表头为null或链表只有一个节点,无需反转,直接返回
            if (null == head || null == head.child){
                return head;
            }
            // 当前节点的前一个节点
            Node pre = null;
            // 当前节点
            Node cur = head;
            // 当前节点的后一个节点
            Node next = null;
            while (cur != null){
                next = cur.child; //next节点指向当前节点的后一个节点
                cur.child = pre;//当前节点的child指向当前节点的前一个节点,反转的关键,此时链表断开
                pre = cur;// 当前节点的前一节点向后移动
                cur = next;// 当前节点向后移动
            }
            return pre;
        }
    
        public static class Node<E>{
            E item;
            Node child;
            public Node(E item){
                this.item = item;
            }
        }
    }
    
    

    测试代码

    
    public class LinkedListTest {
        LinkedList.Node node = null;
    
        @Before
        public void init(){
            LinkedList.Node node1 = new LinkedList.Node(10);
            LinkedList.Node node2 = new LinkedList.Node(20);
            LinkedList.Node node3 = new LinkedList.Node(30);
            LinkedList.Node node4 = new LinkedList.Node(40);
            node = node1;
            node1.child = node2;
            node2.child = node3;
            node3.child = node4;
    
        }
    
        @Test
        public void testReverse(){
            LinkedList.show(node);
            System.out.println("----------------------");
            LinkedList.Node reverseNode =LinkedList.reverse(node);
            LinkedList.show(reverseNode);
        }
    }
    
    
    展开全文
  • * java反转单向链表方法 * @author mengfeiyang * */ public class LinkReverse2 { public static void main(String[] args) { /**链表构造*/ Node node1 = new Node(1); Node node2 = new Node(2); Node ...
    package demo6;
    
    /**
     * java反转单向链表方法
     * @author mengfeiyang
     *
     */
    public class LinkReverse2 {
        public static void main(String[] args) {
        	/**链表构造*/
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
            Node node5 = new Node(5);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
             
            show(node1);
            System.out.println("反转过程:");
             
            Node head = reverse(node1);//反转
            System.out.println("反转后:");
            show(head);        
        }
        static void show(Node head){
            while(head != null){
                System.out.print(head.val+">");
                head = head.next;
            }
        }
        public static Node reverse(Node head){
        	Node cur = head;
        	Node post = head.next;
        	head.next = null;
        	
    		show(cur);
    		System.out.println();
        	while(post!=null){    //初始:cur=1
        		Node tmp = post;  //首次迭代:tmp = 2,第二次:tmp=3,第三次:tmp=4;
        		post = post.next; //post = 3,第二次:post=4,第三次:post=5
        		tmp.next = cur; //2>1,第二次:3>2>1,第三次:4>3>2>1
        		cur = tmp; //链表结构:2>1,第二次:3>2>1,第三次:4>3>2>1
        		show(cur);
        		System.out.println();
        	}
        	return cur;
        }
         
        static class Node{
            int val;
            Node next;
            Node(int val){
                this.val = val;
                //this.next = null;
            }
        }
    }
     

    执行过程及结果:

    1>2>3>4>5>反转过程:
    1>
    2>1>
    3>2>1>
    4>3>2>1>
    5>4>3>2>1>
    反转后:
    5>4>3>2>1>

    转载于:https://my.oschina.net/u/2391658/blog/693281

    展开全文
  • * 单向链表的创建 * 要实现的功能包括: * 初始化 * 返回长度,即节点个数 * 插入、删除节点 * 根据索引获取节点 * 根据节点获取索引 * 判断是否为空 * * 单项链表的核心在于节点类,有了节点类,才能更好...

    一、java代码

    以下代码直接看反转链表的部分即可:

    package mypackage;
    /**
     * 单向链表的创建
     * 要实现的功能包括:
     * 初始化
     * 返回长度,即节点个数
     * 插入、删除节点
     * 根据索引获取节点
     * 根据节点获取索引
     * 判断是否为空
     *
     * 单项链表的核心在于节点类,有了节点类,才能更好的表示节点之间的链接关系
     *
     * 注意,关于第i个节点的约定,第1个节点是头节点后的第一个节点,依次类推.
     * 我们把第一个节点就称之为第一个节点,注意没有索引的概念
     * 即使有索引的话,也是从1开始的,而不是从0开始的
     */
    
    import java.util.Iterator;
    
    //<T>泛型表示支持任意类型
    class LinkList<T> implements Iterable<T>{
        //记录头节点
        private Node head;
        //记录链表的长度,即节点的个数
        private int N;
    
        //定义节点类,这一步至关重要
        //注意构造方法的参数有一个是next,这个类型是Node,正是我们定义的这个类Node
        //这样的话,我们每个节点就可以传入一个参数,next,然后用当前结点调用.next属性就可以获得下一个节点
        //这就是单项链表链接的核心
        private class Node{
            //数据项和下一个节点项
            T data;
            Node next;
            //构造方法
            public Node(T data, Node next){
                this.data=data;
                this.next=next;
            }
        }
    
        //构造方法
        public LinkList(){
            //初始化头节点,初步的头节点的数据项和下一个节点项都是null,节点个数为0
            //头节点的数据项本身就定义为null,他的作用只是指向链表的第一个由数据的节点而已
            //尾节点的下一个节点项本身就定义为null,表示链表的结束
            this.head=new Node(null,null);
            this.N=0;
        }
    
        //清空链表,使得头节点不指向任何节点,且节点个数为0
        public void clear(){
            head.next=null;
            this.N=0;
        }
    
        //获取节点个数
        public int length(){
            return N;
        }
    
        //判断链表是否为空
        public boolean isEmpty(){
            return N==0;
        }
    
        //直接在尾部添加节点
        public void append(T data){
            Node n=head;
            //找到最后一个节点
            while(n.next!=null){
                n=n.next;
            }
            //创建新节点,最后一个节点的next=null
            Node newnode=new Node(data,null);
            //让当前借点指向新节点
            n.next=newnode;
            N++;
        }
    
    
        //向指定位置插入节点,使得这个位置之前的节点指向这个新节点,
        //这个新节点指向这个位置的原本的那个节点
        //其实就是先打断,再链接
        //i第几个节点,和索引没有任何关系,链表没有索引的概念
        public void insert(int i,T data){
            //如果i==N就代表是要在最后添加
            if(i==N){
                Node n=head;
                while(n.next!=null){
                    n=n.next;
                }
                //创建新节点,最后一个节点的next=null
                Node newnode=new Node(data,null);
                //让当前借点指向新节点
                n.next=newnode;
                N++;
            }
    
            //如果在非最后添加
            else{
    //            从头节点开始循环,循环一次,到第一个节点,循环第i-1次,循环到第i-1个节点
    //            这就找到了第i-1个节点
                Node prenode=head;
                //找到待插入节点的前一个节点
                for (int index=1;index<=i-1;index++){
                    prenode=prenode.next;
                }
    //            第i个节点
                Node curnode=prenode.next;
    //            创建新节点,并且新节点指向第i个节点
                Node newnode=new Node(data,curnode);
                //将前一个节点指向新节点
                prenode.next=newnode;
            }
        }
    
        //返回第i个节点的值
        public T get(int i){
            //从头节点向后循环找,循环1此找打第一个节点,循环i次找到第i个节点
            Node n=head;
            for (int index=1;index<=i;index++){
                n=n.next;
            }
            //找到节点后,返回节点的数据
            return n.data;
        }
        //删除指定位置节点,并返回删除的值
        //删除后将指定位置的前一个节点指向后一个节点
        public T remove(int i){
            //如果删除最后一个节点,直接将最后一个节点的前一个节点next=null,并且N--
            if(i==N){
                Node prenode=head;
                for (int index=1;index<=i-1;index++){
                    prenode=prenode.next;
                }
    //            最后一个节点
                Node curnode=prenode.next;
    //            使最后一个节点的前一个节点指向null
                prenode.next=null;
                N--;
    //            返回最后一个节点的元素值
                return curnode.data;
            }
    
            //如果删除非最后节点
            else{
                //找到i位置的前一个节点,删除后将指定位置的前一个节点指向后一个节点
                Node prenode=head;
                for (int index=1;index<=i-1;index++){
                    prenode=prenode.next;
                }
    //            指定节点
                Node curnode=prenode.next;
    //            指定节点的后一个节点
                Node nextnode=curnode.next;
    //            使得指定节点的前一个节点指向指定节点的后一个节点
                prenode.next=nextnode;
                N--;
    //            返回指定节点的元素
                return curnode.data;
            }
        }
    
        //查找某个节点第一次出现的位置,即是第几个元素,从1开始
        //循环查找,找到就返回,没找到就返回-1
        public int indexOf(T data){
            Node n=head;
            for (int index=1;index<=N;index++){
                n=n.next;
                if(n.data.equals(data)){
                    return index;
                }
                break;
            }
            return -1;
        }
    
        //实现遍历
        //遍历的话,要重写此方法
        @Override
        public Iterator<T> iterator() {
            // 返回的Iterator对象,创建一个内部类实现这个接口
            return new LIterator();
        }
    
        //    创建一个内部类实现Iterator接口
        public class LIterator implements Iterator {
            //        定义一个遍历的节点
            private Node n;
            public LIterator(){
    //            初始化为0索引位置
                this.n=head;
            }
            //重写两个方法
            @Override
            public boolean hasNext() {
    //            这个方法判断是否超出最大索引,如果超出会停止遍历
                return n.next!=null;
            }
    
            @Override
            public Object next() {
    //            这个方法会遍历得每个节点
                n=n.next;
                return n.data;
            }
        }
    
        //反转单向链表
        public void reverse(){
            //如果链表为空,直接返回
            if(isEmpty()){
                return;
            }
            //如果链表不为空,调用反转方法,初始传入的是头节点后的第一个节点
            else{
                reverse(head.next);
            }
        }
        //反转的主要方法,注意这个方法是有返回值的,返回传入的这个节点
        //判断如果这个节点后的下一个节点为空,
        //说明这个节点就是最后一个节点,让头节点指向这个节点,并返回这个节点
        //如果这个节点不是最后一节点,递归调用此方法,这时传入的参数是下一个节点了
        //递归函数后的语句保留现状,等待递归完毕返回后再执行
        //递归函数的返回值就是下一个节点,返回后,让下一个节点指向当前结点,并让当前结点指向null
        //这样的话从第一个节点开始递归调用,直到最后一个节点,然后递归返回,再执行每次递归后的语句
        //最后整个反转就完成了
        public Node reverse(Node curnode){
            if(curnode.next==null){
                head.next=curnode;
                return curnode;
            }
            //函数的返回值就是传入的节点参数,prenode返回的是curnode.next
            //也就是让后一个节点反转指向前一个节点
            //让前一个节点指向指向null
            Node prenode=reverse(curnode.next);
            prenode.next=curnode;
            curnode.next=null;
            return curnode;
        }
    }
    
    
    //测试
    public class MyJava {
        public static void main(String[] args) {
    //        创建一个链表
            LinkList<Object> list = new  LinkList<>();
    //        添加节点节点
            list.append(1);
            list.append(2);
            list.append(3);
    
    
            //开始遍历
            for(Object ls:list){
                System.out.println("遍历元素---"+ls);
            }
    
            //反转链表
            list.reverse();
            System.out.println("-------------------");
            //反转后的链表
            for(Object ls:list){
                System.out.println("反转后遍历元素---"+ls);
            }
    
            //       返回节点个数
            int length1 = list.length();
            System.out.println("元素个数"+length1);
    
            //        插入节点
            list.insert(2, 100);
            //开始遍历
            for(Object ls:list){
                System.out.println("插入节点后遍历元素---"+ls);
            }
    
            //       删除节点
            Object remove = list.remove(1);
            System.out.println("删除指定位置处的节点元素是"+remove);
            //开始遍历
            for(Object ls:list){
                System.out.println("删除节点后遍历节点元素---"+ls);
            }
    
    
            //     返回第几个节点元素
            System.out.println("第1个节点的元素是"+list.get(1));
    
            // 返回某个值的位置
            System.out.println("指定节点元素对应的位置为"+list.indexOf(100));
    
            //        清空
            list.clear();
    
            //        是否为空
            System.out.println("判断是否为空"+list.isEmpty());
        }
    }
    

    结果:
    在这里插入图片描述

    二、递归的理解

    要反转链表,就要依次反转每个节点,还得让头节点指向反转后的第一个节点,也就是原链表的最后一个节点。
    假设我们的链表依次是head,1,2,3,因为如果要反转1,就是让1指向null,就必须先反转2,让2指向1,否则如果先让1指向null,那么我们就找不到2了,除非你采取某种方式一次保存每个节点,但是太麻烦。
    因此我们要反转原链表的某个节点就必须反转这个节点的下一个节点,这个时候就是要使用递归,递归结束的条件是最后一个节点。
    递归结束时,让head指向这个节点,同时返回这个节点,而返回的这个节点作为上一级的参数继续执行递归后的语句,依次类推,最终得到结果。
    代码如下:

    //反转单向链表
        public void reverse(){
            //如果链表为空,直接返回
            if(isEmpty()){
                return;
            }
            //如果链表不为空,调用反转方法,初始传入的是头节点后的第一个节点
            else{
                reverse(head.next);
            }
        }
        //反转的主要方法,注意这个方法是有返回值的,返回传入的这个节点
        //判断如果这个节点后的下一个节点为空,
        //说明这个节点就是最后一个节点,让头节点指向这个节点,并返回这个节点
        //如果这个节点不是最后一节点,递归调用此方法,这时传入的参数是下一个节点了
        //递归函数后的语句保留现状,等待递归完毕返回后再执行
        //递归函数的返回值就是下一个节点,返回后,让下一个节点指向当前结点,并让当前结点指向null
        //这样的话从第一个节点开始递归调用,直到最后一个节点,然后递归返回,再执行每次递归后的语句
        //最后整个反转就完成了
        public Node reverse(Node curnode){
            if(curnode.next==null){
                head.next=curnode;
                return curnode;
            }
            //函数的返回值就是传入的节点参数,prenode返回的是curnode.next
            //也就是让后一个节点反转指向前一个节点
            //让前一个节点指向指向null
            Node prenode=reverse(curnode.next);
            prenode.next=curnode;
            curnode.next=null;
            return curnode;
        }
    

    主要的流程图如下(横着手机看,注意①②③----步骤):
    在这里插入图片描述

    三、递归的步骤

    1. 找到递归的终止条件:递归应该在什么时候结束?-----这里的结束条件就是curnode.next==null
    2. 找到返回值:应该给上一级返回什么信息?-----这里返回的信息就是 return curnode
    3. 本级递归应该做什么:在这一级递归中应该完成什么任务?-----prenode.next=curnode,curnode.next=null,head.next=curnode
    展开全文
  • Java实现单向链表反转

    2020-08-27 21:30:19
    主要为大家详细介绍了Java实现单向链表反转,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • javaJava实现单向链表反转.pdf
  • JAVA实现单向链表反转

    千次阅读 2013-06-04 03:11:23
    上一篇《Java实现单向链表反转》中存在一个last是从前往后反转的。本片文章要实现的是从后往前反转。大体思路差不多。就是在临时变量.cur,pre的替换保存花费了些心思。整理一下一下,下面是可运行的Java代码。 ...

    《单向链表反转》
    最近正在面试,求职Android应用方向的工作。基础知识还可以,但是算法,呵呵。做手机客户端的基本涉及算法不多,大多是架构设计,解耦,以及功能优化,UI,IO等。好了废话不多说。进入正题!

    单向链表,你懂得。再此不多做解释。单向链表的反转,时间复杂度,空间复杂度低一些才是好算法吗。基本目前是做到了O(n).思路就是,声明三个引用pre,cur,tempNext,pre,cur分别指向第一个元素和第二个元素。tempNext存住第三个元素的引用。反转前两个,p2---->p1 (注意此时p2.next 已断开)需要原来指向第二个的引用指向第三个,既pre,cur移动到p2,p3 ,也就是pre 引用p2, cur引用p3 .跟第一次pre,cur分别指向p1,p2类似,如此往复下去.
    需要注意的几点,
    1 本身JAVA代码,需要注意Java是值传递还是引用传递。如果不注意的话,变量交换就会有问题。真的,亲!
    2 各种临时变量的记录。不要绕晕了。同时也要注意上一点。 



    上代码!!!自己写的,可运行。

    </pre><pre name="code" class="java">package com.main;
    
    public class Main  {
    
    	public static void main(String[] args) {
    		String [] str={"11","2","45","67","23","44","55","89","74","10"};
    		
    		RevertListfromHead rl= new RevertListfromHead(str);
    
    	}
    
    }
    package com.main;
    
    public class RevertListfromHead {
    	
    	
    	public RevertListfromHead(String[] str) {
    
    		MyLinkList mList = new MyLinkList(str);
    
    		mList.printList(mList.head);
    
            System.out.println("--------------------------");
    		System.out.println("after revert list is ");
    
    		mList.head=mList.revertLinkedList(mList.head);
    		mList.printList(mList.head);
    	}
    	
    	class MyLinkList {
    		private Node head;
    
    
    		private int mlength; 
    
    		public MyLinkList(String[] str) {
    
    			head = new Node(str[0]);
    			Node currentNode = head;
    			for (int i = 1; i < str.length; i++) {
    
    				currentNode.next = new Node(str[i]);
    
    				currentNode = currentNode.next;
    				
    			}
    			mlength = str.length;
    		}
    
    		public Node revertLinkedList(Node _head) {
    
    			int sum=0;
    			if (null == _head) {   
    	            return head;   
    	        }   
    	        Node pre = _head;   
    	        Node cur = _head.next;   
    	        Node tempnext;   
    	        while (null != cur) {   
    	        	tempnext = cur.next;   
    	            cur.next=pre;   
    	            pre = cur;   
    	            cur = tempnext;  
    	            sum++;
    	        }   
    	        //将原链表的头节点的下一个节点置为null,再将反转后的头节点赋给head      
    	        head.next=null;   
    	        head = pre;   
    	        
    	        return head;   
    	}
    
    	public void printList(Node _head) {
    			Node tempNode = _head;
    			while (tempNode != null) {
    				System.out.println("current data is : " + tempNode.data);
    				tempNode = tempNode.next;
    			}
    		}
    
    	}
    
    	static class Node {
    		String data;
    		Node next;
    
    		public Node(String _data) {
    			this.data = _data;
    		}
    	}
    
    }
    展开全文
  • private class LIterator implements java.util.Iterator{ private LinkList.Node n; public LIterator() { this.n = head; } @Override public boolean hasNext() { return n.next!=null; }...
  • 单向链表 反转链表Problem statement: Given a linked list reverse it without using any additional space (In O(1) space complexity). 问题陈述:给定的链表在不使用任何额外空间的情况下将其反向(O(1)空间...
  • java实现单向链表反转

    2019-09-18 09:51:49
    //将原链表的头节点的下一个节点置为null,再将反转后的头节点赋给head     head.next= null ;   head = pre;      return  head;   }    ...
  • 单向链表反转

    2021-05-30 10:42:27
    * @description: 单向链表反转 * @author: zhaozhenwei * @create: 2021-05-30 09:43 **/ public class ListInversion { public static void main(String[] args) { Node listInversion = createListInversio
  • Java实现单向链表反转示例

    千次阅读 2019-02-15 12:52:11
    例如有一单向链表 54-&gt;30-&gt;37-&gt;61-&gt;1-&gt;60-&gt;25-&gt;76-&gt;60-&gt;95 原链表头节点54,尾节点:95 实现效果: 95-&gt;60-&gt;76-&gt;25-&gt;...
  • 单向链表反转(逆置) //定义单链表的节点 public class ListNode { int data; ListNode next; public ListNode(int val) { this.data = val; } } 方法一:迭代法(遍历) //单向链表反转,迭代反转 public ...
  • 下面的程序示例演示了如何构建链表节点,向单向链表插入节点、删除节点、反转单向链表和串联两个单向链表:import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt...
  • Leetcode206 反转链表 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list 博主Github:https://github.com/GDUT-Rp/LeetCode 题目: 反转一个单链表 示例 1: 输入: 1->2->...
  • Java 链表 链表反转

    2016-02-18 09:53:28
    链表:单向链表 双向链表 单向循环链表 双向循环链表 链表的反转. 定义了链表的基本使用, 对链表增加了索引, 使用两种方式(递归和循环)对链表进行反转操作. 单向链表: public class SinglyChain {  ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,098
精华内容 2,039
关键字:

java单向链表的反转

java 订阅