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

初级算法:反转链表

程序员文章站 2024-03-06 21:25:08
...

反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

package com.LinkList;

import javax.sound.midi.Soundbank;

public class ReverseList {
	//迭代算法
//	public ListNode reverseList(ListNode head) {
//		ListNode itr = head;
//		ListNode pre = null;
//		ListNode tempNext = null;//暂存下一个
//		while(head!=null) {
//			tempNext = head.next;
//			if(tempNext!=null) System.out.println(tempNext.val);
//			head.next = pre;
//			pre = head;
//			if(pre!=null) System.out.println("pre:"+pre.val);
//			if(tempNext!=null) head = tempNext;
//			else break;
//		}
//		return head;
//	}
	
	public ListNode reverseList(ListNode head) {
		if(head==null) return null;
		ListNode a = head;
		ListNode b = head.next;
		ListNode result = trans(a, b);
		head.next = null;//头部没有处理
		return result;
	}
	public ListNode trans(ListNode a,ListNode b) {
		if(b.next==null) {
			b.next = a;
			return b;
		}
		ListNode temp = b.next;
		b.next = a;
		return trans(b, temp);
		
	}
	public static void main(String[] args) {
		ListNode listNode = new ListNode(1);
		listNode.next = new ListNode(2);
		listNode.next.next = new ListNode(3);
		new ReverseList().reverseList(listNode);
	}
}