Java语言实现反转链表代码示例

发布时间：2020-12-14 22:13:28 所属栏目：Java 来源：网络整理

导读：问题描述定义一个函数，输入一个链表的头结点，反转该链表并输出反转后的链表的头结点。链表结点如下： public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} 思路1：要想反转链表，对于结点i，我们要把它的ne

问题描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后的链表的头结点。链表结点如下：

public class ListNode {
  int val;
  ListNode next = null;
  ListNode(int val) {
    this.val = val;
  }
}

思路1：

要想反转链表，对于结点i，我们要把它的next指向它的前趋，因此我们需要保存前趋结点，同时，如果我们已经把i的next重新赋值，会无法找到i的后继，因此，在重新赋值之前，我们要保存i的后继。

代码：

public ListNode ReverseList(ListNode head) {
    if(head == null){
      return null;
    }
    ListNode rHead = null;
    ListNode prior = null;//store prior
    ListNode q = head;//store current
    while(q != null){
      ListNode next = q.next;//store the next
      if(next == null){
        rHead = q;
      }
      q.next = prior;
      prior = q;
      q = next;
    }
    return rHead;
  }

思路2：

使用递归的思想（暂时没有想到，因为如果用递归的话，每次应该是：链表的第一个结点<―递归返回的链表的尾指针，但是这样的话就无法获得反转后的头指针了。）后面再思考吧。

总结

以上就是本文关于Java语言实现反转链表代码示例的全部内容，感兴趣的朋友可以参阅：Java编程删除链表中重复的节点问题解决思路及源码分享、Java编程实现从尾到头打印链表代码实例以及本站其他相关专题，希望对大家有所帮助。如有不足之处，欢迎留言指出。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!