欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单向链表的反转

程序员文章站 2024-03-21 14:49:16
...

遍历法

static Node reverse(Node head){
  if(head == null){
    return null;
  }
  Node pre = head;
  Node cur = head;
  Node reHead = null;

  //如果当前节点为空结束循环
  while(cur != null){
    //保存下一个节点以免丢失
    Node temp = cur.next;
    //1.对pre和cur结点的关系进行反转。本来是pre指向cur的,用下面这条代码能够把cur指向pre。
    cur.next = pre;
    //2.如果下一个结点为空,那他就是反转链表的头结点
    if(temp == null)
      rehead = cur;
    
    //上一个节点已经反转完成,现在要移动到下一个节点。
    pre = cur;
    cur = temp;

    return rehead;
    
  }
}


//简化版
static Node reverse(Node head){
  Node pre = null;
  Node cur = null;
  while(head != null){
    temp = head.next;
    head.next = pre;

    pre = head;
    head = temp;
  }
  return pre;
}

 

递归

static Node reverse(Node head){
  //我们从原链表的头结点开始
  Node cur = head;
  //递归到原链表的尾节点结束。递归到了尾节点的时候就返回当前节点
  if(cur == null || cur.next == null){
    return cur;
  }else{
    Node reHead = reverse(cur.next);
    cur.next.next = cur;
    cur.next = null;
    return reHead;
  }
}

内置法

LinkedList没有提供反转链表的相关函数,以下是通过foreach实现链表反转
static LinkedList reverse(LinkedList linkedList) {
    LinkedList<Object> newLinkedList = new LinkedList<>();
    for (Object object : linkedList) {
        newLinkedList.add(0, object);
    }
    return newLinkedList;
}