package dsa.linkedlist;
public class Node<E>{
E data;
Node<E> next;
}
package dsa.linkedlist;
public class ReverseLinkedListRecursively {
public static void main(String args[]) {
ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();
SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);
System.out.println("Original List : " + originalList.toString());
originalList.start = reverser.reverse(originalList.start);
System.out.println("Reversed List : " + originalList.toString());
}
public Node<Integer> reverse(Node<Integer> list) {
if (list == null || list.next == null)
return list;
Node<Integer> nextItem = list.next;
list.next = null;
Node<Integer> reverseRest = reverse(nextItem);
nextItem.next = list;
return reverseRest;
}
private SinglyLinkedList<Integer> getLabRatList(int count) {
SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
for (int i = 0; i < count; i++) {
sampleList.add(i);
}
return sampleList;
}
}
/*
* SAMPLE OUTPUT Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Reversed List : 9,
* 8, 7, 6, 5, 4, 3, 2, 1, 0
*/
package dsa.linkedlist;
/**
* This is a singly linked list with no prev pointer.
* @author Braga
* @param <E>
*/
public class SinglyLinkedList<E> {
Node<E> start;
int size;
public SinglyLinkedList(){
start = null;
size = 0;
}
//insertAtLast
public void add(E data){
insertAtLast(data);
}
public void insertAtLast(E data){
if(size==0){
start = new Node<E>();
start.next = null;
start.data = data;
}else{
Node<E> currentNode = getNodeAt(size-1);
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = null;
currentNode.next = newNode;
}
size++;
}
public void insertAtFirst(E data){
if(size==0){
start = new Node<E>();
start.next = null;
start.data = data;
}else{
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = start;
start = newNode;
}
size++;
}
public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{
if(nodePos>=size || nodePos<0){
throw new ArrayIndexOutOfBoundsException();
}
Node<E> temp = start;//Move pointer to front
int counter = 0;
for(;counter<nodePos;counter++){
temp = temp.next;
}
return temp;
}
public void insertAt(int position, E data){
if(position == 0){
insertAtFirst(data);
}else if(position==size-1){
insertAtLast(data);
}else{
Node<E> tempNode = getNodeAt(position-1);
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = tempNode.next;
tempNode.next = newNode;
size++;
}
}
public Node<E> getFirst(){
return getNodeAt(0);
}
public Node<E> getLast(){
return getNodeAt(size-1);
}
public E removeAtFirst(){
if(size==0){
throw new ArrayIndexOutOfBoundsException();
}
E data = start.data;
start = start.next;
size--;
return data;
}
public E removeAtLast(){
if(size==0){
throw new ArrayIndexOutOfBoundsException();
}
Node<E> tempNode = getNodeAt(size-2);
E data = tempNode.next.data;
tempNode.next = null;
size--;
return data;
}
public E removeAt(int position){
if(position==0){
return removeAtFirst();
}else if(position == size-1){
return removeAtLast();
}else{
Node<E> tempNode = getNodeAt(position-1);
E data = tempNode.next.data;
tempNode.next = tempNode.next.next;
size--;
return data;
}
}
public int size(){
return size;
}
public String toString(){
if(size==0){
return "";
}else{
StringBuilder output = new StringBuilder();
Node<E> tempNode = start;
while(tempNode.next!=null){
output.append(tempNode.data).append(", ");
tempNode = tempNode.next;
}
output.append(tempNode.data);
return output.toString();
}
}
}
分享到:
相关推荐
move to front find keys 找关键字
DSA实验室数据结构和算法实验室资料库结构 Lab 1: Introduction to GIT and the work-flow of the lab + starting with Singly Linked Lists作业1: 1.11.2 (额外功劳!) Lab 2: Circular Linked Lists and Doubly...
singly linked lists 126 M malloc 112 Mathematical Induction 42 Matrix adjacency 80 Median of three 152 Message in a hypercube 79 Message passing in a hypercube 78 Moveto 52 ...
线性表 Linear List 二叉树 Binary Tree Depth_First Search 深度优先搜索 singly linked lists 单链表 2. 单项选择题 1、数据结构是一门研究非数值计算的程序设计问题中数据元素的 、数据信息在计算机中的存储结构...
The chapter on data structures covers singly linked lists, doubly linked circular lists, hash tables and binary trees. Test programs are presented for all these data structures. There is a chapter on...
Singly Linked Lists Memory Management Timers String Handling Utility and Error Functions 22. GTK's rc Files Functions For rc Files GTK's rc File Format Example rc file 23. Writing Your Own Widgets ...
/*归并法:用于合并两个链表*/ /* * SCs in different cases * author: Whywait ... // merge two sorted Singly linked lists // LA, LB and the return one ( LC ) all have a head node // all the
a、是否使用内核Singly-linked lists; b、是否使用处理线程(工作线程和处理线程分开); c、是否使用内核锁来同步链表。 8、可以实现集群服务器模式的通讯(有客户端socket); 9、可以单独设置每个连接的Data项来...
Singly and Doubly Linked Lists 2-2. Structure of a Hash Table 2-3. Structure of an N-ary Tree 2-4. The GNOME Dependency Tree 2-5. GDK Event Flow 2-6. Widget Appearances 3-1. Running the configure ...
* allows changing of column width in redonly editors. Can be switchoed off in EditOptions or set compiler define TOTALREADONLY + wpDisableSelectAll in EditOptionsEx2 * changed reformat/repaint after...
专案0 * 1 * 2 * 3 * 4 *更多功能5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 *更多 13 * 预处理器14 * Structures_typedef 15 * Function_pointers 16 * Variadic_functions 17 *单链接列表18 * More_singly_linked_lists 。...
合并K个排序链表 题目描述: 解题思路: 第一种:这个方法比较暴力,思路也很简单。...# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class
2.1 Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Searching . . . . . . . . . . . . . . . . ...
数据结构数据结构是一种组织数据的方式,以便可以有效地使用它。内容