通过Java函数来实现链表反转的方法是什么?
发布时间:2023-07-04 06:47:52
实现链表反转的方法有多种,下面我将介绍一种通过Java函数来实现链表反转的方法,包括链表节点的定义、反转函数的编写、测试示例等。本方法基于迭代的思路实现链表反转。
首先,我们需要定义一个链表节点类,包含一个值域和一个指向下一个节点的指针。代码如下:
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
接下来,我们定义一个函数 reverseList() 来实现链表反转。该函数的输入参数是链表的头节点,返回值是反转后的链表的头节点。
函数具体的实现思路是用两个指针 prev 和 curr,分别指向当前节点的前一个节点和当前节点。从头开始遍历链表,依次将 curr 的指针指向 prev,然后将 prev 和 curr 都向后移动一个节点,直到遍历完链表。
最后,将链表的最后一个节点指向 prev,并返回新的头节点。代码如下:
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
为了验证代码的正确性,我们可以编写一个简单的测试示例。首先创建一个链表,然后输出原链表的节点值,接着调用 reverseList() 函数将链表反转,最后输出反转后链表的节点值。
public static void main(String[] args) {
// 创建链表 1 -> 2 -> 3 -> 4 -> 5
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
// 输出原链表节点值
ListNode curr = node1;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
// 反转链表
ListNode reversedHead = reverseList(node1);
// 输出反转后链表节点值
curr = reversedHead;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
}
运行以上代码,将得到如下输出结果:
1 2 3 4 5 5 4 3 2 1
可以看到,原链表的节点值为 1 2 3 4 5,经过 reverseList() 函数反转后,链表的节点值变为 5 4 3 2 1,符合预期结果。
综上所述,通过以上提供的Java函数实现链表反转的方法,可以有效地实现链表的反转操作。
