极客教程Java 反转LinkedList
假设你已经通过了java中的LinkedList并了解了链接列表。这篇文章包含了反转链接列表的不同例子，如下所示： 1. 通过编写我们自己的函数（使用额外的空间）：reverseLinkedList()方法包含反转字符串对象的逻辑。 通过编写我们自己的函数（使用额外的空间）： reverseLinkedList()方法包含在一个链接列表中反转字符串对象的逻辑。该方法以一个链表为参数，以相反的顺序遍历所有的元素，并将其添加到新创建的链表中。
算法： 步骤
1.创建一个有n个元素的链表
2.创建一个空的链表，它将被用来存储反转的元素
3.开始从’n’到’0’遍历列表，并将这些元素存储在新创建的列表中。
4.这些元素将按以下顺序存储：n，n-1，n-2，……0 步骤
5.将列表返回给调用者并打印出来
例子：
第1步： LL: 1 -> 2 -> 3 -> 4 -> 5 其中’LL’是有n个元素的链接列表
第2步： ‘Rev’是一个空链表。
第3步:开始遍历，下面的遍历是遍历时的中间步骤
第1步： Rev: 5
第2步： Rev: 5 -> 4
第3步： Rev: 5 -> 4 -> 3
第4步： Rev: 5->4->3->2
第5步: Rev: 5 -> 4 -> 3 -> 2 -> 1
第4步：‘LL’的第n个元素被存储在’Rev’的第0个位置。
LL的n-1个元素被存储在Rev的第1个位置，以此类推……。
第5步：返回Rev：5->4->3->2->1到调用函数。
// Java program for reversing linked list using additional space
import java.util.*;
public class LinkedListTest1 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<String> linkedli = new LinkedList<String>();
// Appending elements at the end of the list
linkedli.add("Cherry");
linkedli.add("Chennai");
linkedli.add("Bullet");
System.out.print("Elements before reversing: " + linkedli);
linkedli = reverseLinkedList(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList<String> reverseLinkedList(LinkedList<String> llist)
{
LinkedList<String> revLinkedList = new LinkedList<String>();
for (int i = llist.size() - 1; i >= 0; i--) {
// Append the elements in reverse order
revLinkedList.add(llist.get(i));
}
// Return the reversed arraylist
return revLinkedList;
}
}
时间复杂度： O(n) 空间复杂度： O(n) 注意： 由于我们使用额外的内存空间来存储所有反转的’n’元素，空间复杂度为O(n)。
输出
Elements before reversing: [Cherry, Chennai, Bullet]
Elements after reversing: [Bullet, Chennai, Cherry]
2.通过编写我们自己的函数（不使用额外的空间）： 在前面的例子中，另外使用了一个链接列表来存储所有反转的元素，这需要更多的空间。为了避免这种情况，可以用同一个链表来进行反转。
算法：
1.创建一个有n个元素的链表 1.循环运行n/2次，其中’n’是链表中元素的数量。
2.在第一遍中，交换第一个和第n个元素
3.在第二遍中，交换第二个和第(n-1)个元素，以此类推，直到你到达链接列表的中间。
4.循环结束后返回链接列表。
示例:
输入: 1 -> 2 -> 3 -> 4 -> 5
1st pass: (swap first and nth element)
5 -> 2 -> 3 -> 4 -> 1
2nd pass: (swap second and (n-1)th element)
5 -> 4 -> 3 -> 2 -> 1
3rd pass: (reached mid, Terminate loop)
5 -> 4 -> 3 -> 2 -> 1
输出: 5 -> 4 -> 3 -> 2 -> 1
// Java program for reversing an arraylist without
// using any additional space
import java.util.*;
public class LinkedListTest2 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<Integer> linkedli = new LinkedList<Integer>();
// Appending elements at the end of the list
linkedli.add(new Integer(1));
linkedli.add(new Integer(2));
linkedli.add(new Integer(3));
linkedli.add(new Integer(4));
linkedli.add(new Integer(5));
System.out.print("Elements before reversing: " + linkedli);
// Calling user defined function for reversing
linkedli = reverseLinkedList(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList<Integer> reverseLinkedList(LinkedList<Integer> llist)
{
for (int i = 0; i < llist.size() / 2; i++) {
Integer temp = llist.get(i);
llist.set(i, llist.get(llist.size() - i - 1));
llist.set(llist.size() - i - 1, temp);
}
// Return the reversed arraylist
return llist;
}
}
时间复杂度： O(n/2) 空间复杂度： O(1)
输出
Elements before reversing: [1, 2, 3, 4, 5]
Elements after reversing: [5, 4, 3, 2, 1]
3.通过使用Collections类： Collections是java.util包中的一个类，它包含各种静态方法，用于搜索、排序、反转、查找最大值、min….等。我们可以利用内置的Collections.reverse()方法来反转一个链接列表。它接收一个列表作为输入参数，并返回反转的列表。
注意：Collections.reverse()方法使用的算法与 “通过编写我们自己的函数（不使用额外的空间） ” 相同 。
// Java program for reversing a linked list using
// In-built collections class
import java.util.*;
public class LinkedListTest3 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<Integer> linkedli = new LinkedList<Integer>();
// Appending elements at the end of the list
linkedli.add(new Integer(1));
linkedli.add(new Integer(2));
linkedli.add(new Integer(3));
linkedli.add(new Integer(4));
linkedli.add(new Integer(5));
System.out.print("Elements before reversing: " + linkedli);
// Collections.reverse method takes a list as a
// parameter and returns the reversed list
Collections.reverse(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
}
时间复杂度： O(n/2) 空间复杂度： O(1)
输出
Elements before reversing: [1, 2, 3, 4, 5]
Elements after reversing: [5, 4, 3, 2, 1]
4.反转用户定义对象的链接列表： 创建一个Employee类，用于创建用户定义的对象，EmployeeID、EmployeeName、DepartmentName是类的变量，在构造函数中被初始化。创建一个链接列表，只接受Employee（用户定义）对象。这些对象通过add()方法被添加到链接列表中。printElements()方法被用来遍历链接列表中所有的用户定义对象，并打印每个对象的雇员ID、姓名和部门名称。
// Java program for reversing a linkedlist of user defined objects
import java.util.*;
class Employee {
int empID;
String empName;
String deptName;
// Constructor for initializing the class variables
public Employee(int empID, String empName, String deptName)
{
this.empID = empID;
this.empName = empName;
this.deptName = deptName;
}
}
public class LinkedListTest4 {
public static void main(String[] args)
{
// Declaring linkedList without any initial size
LinkedList<Employee> linkedli = new LinkedList<Employee>();
// Creating user defined objects
Employee emp1 = new Employee(123, "Cherry", "Fashionist");
Employee emp2 = new Employee(124, "muppala", "Development");
Employee emp3 = new Employee(125, "Bullet", "Police");
// Appending all the objects to linkedList
linkedli.add(emp1);
linkedli.add(emp2);
linkedli.add(emp3);
System.out.print("Elements before reversing: ");
printElements(linkedli);
// Collections.reverse method takes a list as a parameter
// and returns the reversed list
Collections.reverse(linkedli);
System.out.print("\nElements after reversing: ");
printElements(linkedli);
}
// Iterate through all the elements and print
public static void printElements(LinkedList<Employee> llist)
{
for (int i = 0; i < llist.size(); i++) {
System.out.print("\n EmpID:" + llist.get(i).empID + ", EmpName:"
+ llist.get(i).empName + ", Department:" + llist.get(i).deptName);
}
}
}
时间复杂度： O(n/2) 空间复杂度： O(1)
输出
Elements before reversing:
EmpID:123, EmpName:Cherry, Department:Fashionist
EmpID:124, EmpName:muppala, Department:Development
EmpID:125, EmpName:Bullet, Department:Police
Elements after reversing:
EmpID:125, EmpName:Bullet, Department:Police
EmpID:124, EmpName:muppala, Department:Development
EmpID:123, EmpName:Cherry, Department:Fashionist