每日一题:Java实现单向链表的反转

Love The Way You Lie 2024-04-01 10:40 56阅读 0赞

## 一.问题的分析 ##

实现单向链表的反转其实就是将链表的最后一个结点放在第一位,将倒数第二个节点放在第二位,以此类推.

我们学过链表的的两种插入节点的方法,一种是头插法,一种是尾插法,刚好这两种方式插入的时候结点的顺序正好是相反的,相当如将头插法按尾插法的方式插入,正好就是可以实现链表的插入

## 二.创建结点 ##

class DataNode {
        public Integer id;
        public DataNode next;
    
        public DataNode(Integer id) {
            this.id = id;
        }
    
        @Override
        public String toString() {
            return "DataNode{" +
                    "id=" + id +
                    '}';
        }
    }

### 三.创建单链表 ###

class SingleLinkedList {
        private DataNode head = new DataNode(0);
    
        public DataNode getHead() {
            return head;
        }
    
        //添加链表(尾插法)
        public void add(DataNode newNode) {
            DataNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
            head.id++;
    
        }
    
        //添加链表(头插法)
        public void addByHead(DataNode newNode) {
            newNode.next = head.next;
            head.next = newNode;
            head.id++;
    
        }
    
    
        //遍历节点
        public void list() {
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            System.out.println("此链表共有" + head.id + "个结点");
            DataNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
                System.out.println(temp);
            }
    
    
        }
    }

## 四.实现方法 ##

public class LinkListDemo {
        public static void main(String[] args) {
            SingleLinkedList list = new SingleLinkedList();
            list.addByHead(new DataNode(1));
            list.addByHead(new DataNode(4));
            list.addByHead(new DataNode(6));
            list.addByHead(new DataNode(9));
            list.list();
            reverse(list.getHead());
            list.list();
    
        }
        
         public static void reverse(DataNode head) {
            if (head.next == null || head.next.next == null)
                return;
            DataNode reverseHead = new DataNode(0);
            DataNode temp = head.next;
            DataNode insertNode=temp;
            while (temp != null) {
                temp = temp.next;
                insertNode.next = reverseHead.next;
                reverseHead.next = insertNode;
                insertNode = temp;
    
            }
    
            head.next = reverseHead.next;
    
    
        }
    }

## 五.输出结果 ##

> 此链表共有4个结点  
> DataNode\{id=9\}  
> DataNode\{id=6\}  
> DataNode\{id=4\}  
> DataNode\{id=1\}  
> \-------------------------------  
> 此链表共有4个结点  
> DataNode\{id=1\}  
> DataNode\{id=4\}  
> DataNode\{id=6\}  
> DataNode\{id=9\}

## 六.分析与注意点 ##

当进行链表反转的时候,首先要判断链表是否为空,或者链表仅含有一个结点的时候,此时链表不需要反转,或者无法反转,程序停止.

因为要反转一个链表,并且采用头插法的形式进行插入节点,所以第一步应该是把所有的结点全部都拿出来,然后进行头插法的插入到一个新的头结点.

此时形成一个新的链表为的头结点为reverseHead,此时我们需要考虑的就是如何将reverseHead

"嫁接"到以head为头结点的链表,如何直接令head=reverseHead,(存在于栈中)当方法没有结束的时候,遍历链表,此时是满足要求的,但是当方法结束的时候,head指向的地址仍然是原来的地址,链表并没有发生反转,答案是错误的.那么我们应该考虑的是如何使head的地址不发生改变,使得head可以是反转链表的头结点呢,如果head.next指向reverseHead.next,此时由于是存在于堆之中的,当方法结束的时候,并没有发生改变,head.next的地址仍然是指向reverseHead.next的,此时便可以成功的完成.