单向链表反转迭代算法实现

  • 内容
  • 评论
  • 相关

1 首先创建一个链表

package com.alibaba.LinkedNode;

/**
 * Created by think.
 * Date: 12/11/2018
 * Time: 13:06
 */
public class Node {
    //数据域
    private int date;
    //指针域
    private Node next;

    public Node(int date) {
        this.date = date;
    }

    public int getDate() {
        return date;
    }

    public void setDate(int date) {
        this.date = date;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

然后从最后一个节点开始反转:

package com.alibaba.LinkedNode;

/**
 * Created by think.
 * Date: 12/11/2018
 * Time: 13:10
 */
public class Test {
    public static void main(String[] args) {
        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);

        Node h = head;
        System.out.println("反转前的节点");
        while (h != null) {
            System.out.println(h.getDate() + " ");
            h = h.getNext();
        }

        System.out.println("反转后的节点");
        head = reverse(head);
        while (head != null) {
            System.out.println(head.getDate() + "");
            head = head.getNext();
        }
    }

    public static Node reverse(Node head) {
        // head为上一节点,如果为空链或者当前节点在尾节点,则直接返回
        if (head == null || head.getNext() == null) {
            return head;
        }

        Node reverseHead = reverse(head.getNext());
        //将当前节点的指针域指向前一节点
        head.getNext().setNext(head);
        //将前一节点的指针域设置为null
        head.setNext(null);
        return reverseHead;
    }
}

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注