java实现链表反转

本文为大家分享了java实现链表反转的具体代码，供大家参考，具体内容如下

算法题：实现链表的反转

提供了2种方法，迭代法、递归法。

（为了方便输出可视化，在自定义的listnode中重写了tostring方法。）

/**
 * created by --- on 2021/8/12
 * 以下代码可以直接粘贴进编译器输出
 */
public class reverselist {
 
  public static void main(string[] args) {
    listnode head = new listnode(3, new listnode(5, new listnode(8, new listnode(9))));
    system.out.println("初始链表：" + head);
 
    listnode newlist = reverselist(head);
    system.out.println("使用迭代法反转链表：" + newlist);
 
    listnode newlist2 = reverselist2(null, newlist);
    system.out.println("使用递归法反转链表：" + newlist2);
  }
 
  /**
   * 迭代法
   */
  public static listnode reverselist(listnode head) {
    listnode pre = null;
    listnode cur = head;
    listnode tmp;
    while (cur != null) {
      tmp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    return pre;
  }
 
  /**
   * 递归法
   */
  public static listnode reverselist2(listnode pre, listnode cur) {
    if (cur == null) {
      return pre;
    }
 
    listnode tmp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = tmp;
    return reverselist2(pre, cur);
  }
 
 
}
 
 
/**
 * singly-linked list
 */
class listnode {
 
  int val;
  listnode next;
 
  listnode() {
  }
 
  listnode(int val) {
    this.val = val;
  }
 
  listnode(int val, listnode next) {
    this.val = val;
    this.next = next;
  }
 
  @override
  public string tostring() {
    stringbuilder sb = new stringbuilder(string.valueof(val));
    listnode next = this.next;
    while (next != null) {
      sb.append(next.val);
      next = next.next;
    }
    return sb.tostring();
  }
}

输出结果：

再为大家分享一段java实现链表反转的三种方式

分别通过栈、递归、指针的方式实现：

import java.util.stack;
 
public class reverselinkedlist {
 
    public static void main(string[] args) {
        reverselinkedlist reverselinkedlist = new reverselinkedlist();
        reverselinkedlist.test();
    }
 
    public void test() {
        node node1 = new node(1);
        node node2 = new node(2);
        node node3 = new node(3);
        node1.setnext(node2);
        node2.setnext(node3);
        //方法需要替换
        node1 = reversebypointer(node1);
        while (node1 != null) {
            system.out.println(node1.val);
            node1 = node1.getnext();
        }
    }
 
    //栈实现
    private node reversebystack(node head) {
        if (head == null || head.getnext() == null) {
            return head;
        }
        stack<node> stack = new stack<>();
        while (head != null) {
            stack.push(head);
            head = head.getnext();
        }
        head = stack.pop();
        node tmp = head;
        while (!stack.empty()) {
            node node = stack.pop();
            node.setnext(null);
            tmp.setnext(node);
            tmp = node;
        }
        return head;
    }
 
    //递归实现
    private node reversebyrecursion(node head) {
        if (head == null || head.getnext() == null) {
            return head;
        }
        //递归获取当前节点的后一个节点
        node tmp = reversebyrecursion(head.getnext());
        node node = head.getnext();
        head.setnext(null);
        node.setnext(head);
        return tmp;
    }
 
    //指针实现
    private node reversebypointer(node head) {
        if (head == null || head.getnext() == null) {
            return head;
        }
        //pre指针指向前一个节点，初始第一个节点的前节点为空
        node pre = null;
        //tmp指针指向当前节点
        node tmp = null;
        while (head != null) {
            //tmp指针指向head头指针节点
            tmp = head;
            //head头指针向后遍历
            head = head.getnext();
            //反转，设置当前节点的下一个节点为前一个节点
            tmp.setnext(pre);
            //pre指针向后移动，指向当前节点
            pre = tmp;
        }
        return tmp;
    }
 
    private class node {
        private int val;
 
        private node next;
 
        public node(int val) {
            this.val = val;
        }
 
        public node getnext() {
            return next;
        }
 
        public void setnext(node next) {
            this.next = next;
        }
    }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。