我想解决以下任务：
给定一个单链表，编写一个函数来交换元素成对。例如，如果链表为1->2->3->4->5->6->7，则函数应将其更改为2->1->4->3->6->5->7，如果链表为1->2->3->4->5->6，则函数应将其更改为2->1->4->3->6->5
为了做到这一点，我使用了从这里开始的递归方法：http://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list-by-changing-links/，即交换前两个节点，然后在列表的其余部分上递归。我的功能如下：
private static ListNode reorder(ListNode l1) {
if(l1 == null || l1.next == null)
return l1;
ListNode rest = l1.next.next;
//change head
ListNode newHead = l1.next;
//change next of second node
newHead.next = l1;
l1.next = reorder(rest);
return newHead;
}
然而，在输入1 2 3 4 5 6上，我有输出1 4 3 6 5？！我调试了它，但仍然看不出问题出在哪里。有人能解释一下为什么会这样吗？这是全班同学：
public class Swap {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public static void main(String[] args) {
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
ListNode l6 = new ListNode(6);
ListNode l7 = new ListNode(7);
ListNode l8 = new ListNode(8);
ListNode l9 = new ListNode(9);
ListNode l10 = new ListNode(10);
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;
l7.next = l8;
l9.next = l10;
print(l1);
reorder(l1);
System.out.println();
print(l1);
}
private static void print(ListNode l1) {
ListNode current = l1;
while(current != null){
System.out.print(current.val + " ");
current = current.next;
}
}
private static ListNode reorder(ListNode l1) {
if(l1 == null || l1.next == null)
return l1;
ListNode rest = l1.next.next;
//change head
ListNode newHead = l1.next;
//change next of second node
newHead.next = l1;
l1.next = reorder(rest);
return newHead;
}
}
您正在从l1开始打印列表，l1现在是第二个元素。你想打电话给
print(reorder(l1));
这是我做过的递归方法，对我有效。如果有任何问题，请告诉我。
public void pairwiseSwap(Node node){
if(size() == 0){
System.out.println("empty");
return;
}
if(node.next == null){
System.out.println(node.value);
return;
}
Node one = node;
Node two = node.next;
System.out.println(two.value);
System.out.println(one.value);
if(two.next == null)
return;
pairwiseSwap(two.next);
}
您的列表连接不好，您缺少以下链接：
l6.next = l7;
l8.next = l9;
以下是大多数链表重分配问题的解决方案
-
在开始时插入
-
在末尾插入
- 在位置插入
- 获取列表的大小
- 显示列表
- 从列表中删除
- 替换节点
- 搜索列表中的项目位置
-
找到列表的中间"
-
从上次中获取项目
- 反转列表
- 交换列表的节点
- 成对交换列表
- 将最后一个节点作为第一个节点
Node.java
package com.practice.ds.list;
final public class Node<T> {
public Node<T> next = null;
public Node<T> prev = null;
public T data = null;
public Node() {
}
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return "Node [next=" + next + ", prev=" + prev + ", data=" + data + "]";
}
}
LinkedList.java
package com.practice.ds.list;
public class LinkedList<T> {
private Node<T> head = null;
private Node<T> tail = null;
public void insertAtStart(T data) {
throwEmptyDataException(data);
Node<T> node = new Node<T>(data);
if(empty()) {
head = node;
tail = head;
}else {
node.next = head;
head = node;
}
display();
}
public void insertAtEnd(T data) {
throwEmptyDataException(data);
if(empty()) {
insertAtStart(data);
}else {
Node<T> node = new Node<T>(data);
tail.next = node;
tail = node;
display();
}
}
public void insertAtPosition(int position, T data) {
throwEmptyDataException(data);
if (position < 1 || position > size() || empty())
throw new IllegalArgumentException("Can't perform insertion. Please check your inputs");
Node<T> node = head;
Node<T> tempNode = node;
for (int i = 1; i <= size(); i++) {
if (i == position) {
if (node == head) {
insertAtStart(data);
return;
} else {
Node<T> newNode = new Node<T>(data);
tempNode.next = newNode;
newNode.next = node;
display();
break;
}
}
tempNode = node;
node = node.next;
}
}
public boolean delete(int position) {
if (empty() || position < 1 || position > size())
return false;
Node<T> node = head;
Node<T> tempNode = node;
for (int i = 1; i <= size(); i++) {
if(i == position) {
if(node == head) {
head = head.next;
return true;
}else if(node == tail) {
tempNode.next = null;
tail = tempNode;
return true;
}else {
tempNode.next = node.next;
return true;
}
}
tempNode = node;
node = node.next;
}
return false;
}
public T replace(int position, T data) {
throwEmptyDataException(data);
if (empty() || position < 1 || position > size())
return null;
Node<T> node = head;
for (int i = 1; i <= size(); i++) {
if(i == position) {
T replaceData = node.data;
node.data = data;
return replaceData;
}
node = node.next;
}
return null;
}
public boolean search(T data) {
Node<T> node = head;
while(node != null && !node.data.equals(data)) {
node = node.next;
}
return node != null;
}
public T middle() {
Node<T> slowPtr = head;
Node<T> fastPtr = head;
while(fastPtr != null && fastPtr.next != null) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
return empty() ? null : slowPtr.data;
}
public T getElementFromLast(int position) {
if(empty() || position < 1 || position > getSizeIteratively())
return null;
Node<T> firstPtr = head;
Node<T> secondPtr = head;
for(int i = 1;i<=size();i++) {
if(i > position)
firstPtr = firstPtr.next;
if(secondPtr.next == null)
return firstPtr.data;
secondPtr = secondPtr.next;
}
return null;
}
public void reverse() {
Node<T> prev = null;
Node<T> current = head;
Node<T> next = null;
while(current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
swapHeadTail();
displayIteratively();
}
public void reverseRecursively() {
reverseRecursively(head);
swapHeadTail();
display();
}
private Node<T> reverseRecursively(Node<T> node) {
if(node == null || node.next == null)
return node;
Node<T> secondNode = node.next;
node.next = null;
Node<T> reverseRest = reverseRecursively(secondNode);
secondNode.next = node;
return reverseRest;
}
private void swapHeadTail() {
Node<T> temp = head;
head = tail;
tail = temp;
}
public void swapPairwise() {
if(empty())
return;
Node<T> firstNode = head;
Node<T> secondNode = firstNode.next;
while(firstNode != null && secondNode != null) {
swap(firstNode.data, secondNode.data);
firstNode = firstNode.next;
if(firstNode != null)
secondNode = firstNode.next;
}
}
public void swap(T firstData, T secondData) {
throwEmptyException();
throwEmptyDataException(firstData);
throwEmptyDataException(secondData);
if(firstData.equals(secondData))
throw new IllegalArgumentException(firstData +" & "+ secondData+" both are the same. Can't swap");
Node<T> firstDataPtr = head;
Node<T> prevfirstDataPtr = firstDataPtr;
while (firstDataPtr != null && !firstDataPtr.data.equals(firstData)) {
prevfirstDataPtr = firstDataPtr;
firstDataPtr = firstDataPtr.next;
}
Node<T> secondDataPtr = head;
Node<T> prevSecondDataPtr = secondDataPtr;
while (secondDataPtr!= null && !secondDataPtr.data.equals(secondData)) {
prevSecondDataPtr = secondDataPtr;
secondDataPtr = secondDataPtr.next;
}
if(!(firstDataPtr == null || secondDataPtr == null)) {
// either first node or second node is head node
if (firstDataPtr == head)
head = secondDataPtr;
else if (secondDataPtr == head)
head = firstDataPtr;
// either first node or second node is tail node
if (firstDataPtr == tail)
tail = secondDataPtr;
else if (secondDataPtr == tail)
tail = firstDataPtr;
// getting the next pointer of both nodes
Node<T> nextFirstDataPtr = firstDataPtr.next;
Node<T> nextSecondDataPtr = secondDataPtr.next;
// swapping the nodes
prevfirstDataPtr.next = secondDataPtr;
secondDataPtr.next = nextFirstDataPtr;
prevSecondDataPtr.next = firstDataPtr;
firstDataPtr.next = nextSecondDataPtr;
// checking if both node is adjacent node
// if both nodes are adjacent re-adjust the pointer
if(nextFirstDataPtr == secondDataPtr) {
secondDataPtr.next = firstDataPtr;
} else if(nextSecondDataPtr == firstDataPtr) {
firstDataPtr.next = secondDataPtr;
}
} else
throw new IllegalArgumentException("Either "+firstData+" or "+secondData+" not present in the list");
displayIteratively();
}
public void setLastNodeAsFirstNode() {
if(empty() || head.next == null) {
return;
}
Node<T> node = head;
Node<T> prevNode = node;
while (node.next != null) {
prevNode = node;
node = node.next;
}
node.next = head;
head = node;
prevNode.next = null;
tail = prevNode;
display();
}
public int getSizeIteratively() {
if (empty())
return 0;
int size = 0;
Node<T> node = head;
while (node != null) {
++size;
node = node.next;
}
return size;
}
public int size() {
return size(head, 0);
}
private int size(Node<T> node, int size) {
return node != null ? size(node.next, ++size) : size;
}
public void displayIteratively() {
Node<T> node = head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public void display() {
display(head);
}
private void display(Node<T> node) {
if (node != null) {
System.out.print(node.data + " ");
display(node.next);
}
}
public void throwEmptyException() {
if (empty())
throw new IllegalArgumentException("List is empty!");
}
private void throwEmptyDataException(T data) {
if (data == null)
throw new IllegalArgumentException("data is null !");
}
public boolean empty() {
return head == null;
}
}
LinkedListTest.java
package com.practice.ds.list;
import java.util.Scanner;
public class LinkedListTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
LinkedList<Integer> list = new LinkedList<>();
boolean exit = false;
do {
System.out.println("n----------------------------------------");
System.out.println("1. Insert at Start");
System.out.println("2. Insert at End");
System.out.println("3. Insert at Position");
System.out.println("4. Get the size of list");
System.out.println("5. Display the list");
System.out.println("6. Delete from the list ");
System.out.println("7. Replace the node ");
System.out.println("8. Search item position in the list ");
System.out.println("9. Find the middle of the list");
System.out.println("10. Get item from the last : ");
System.out.println("11. Reverse the list :: ");
System.out.println("12. Swap the node of the list");
System.out.println("13. Pairwise swap the list");
System.out.println("14. Make last node as first node");
System.out.println("15. Segregate even and odd node");
System.out.println();
int choice = scanner.nextInt();
switch (choice) {
case 1:
try {
System.out.println("Insert the node : ");
int node = scanner.nextInt();
list.insertAtStart(node);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 2:
try {
System.out.println("Insert the node : ");
int node = scanner.nextInt();
list.insertAtEnd(node);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 3:
try {
System.out.println("Enter the position :");
int position = scanner.nextInt();
System.out.println("Insert the node :");
int node = scanner.nextInt();
list.insertAtPosition(position, node);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 4:
try {
System.out.println("Getting the size :: ");
System.out.println("1. Get Iteratively");
System.out.println("2. Get Recursively");
int input = scanner.nextInt();
switch (input) {
case 1:
System.out.println("The size of the list :: " + list.getSizeIteratively());
break;
case 2:
System.out.println("The size of the list :: " + list.size());
break;
default:
System.out.println("Invalid input...!");
break;
}
} catch (Exception e) {
e.printStackTrace();
}
break;
case 5:
try {
System.out.println("Displaying the list :: ");
System.out.println("1. Display Iteratively");
System.out.println("2. Display Recursively");
int input = scanner.nextInt();
switch (input) {
case 1:
list.displayIteratively();
break;
case 2:
list.display();
break;
default:
System.out.println("Invalid input...!");
break;
}
} catch (Exception e) {
e.printStackTrace();
}
break;
case 6:
try {
System.out.println("Enter the position ");
int position = scanner.nextInt();
System.out.println("is Delete :: " + list.delete(position));
} catch (Exception e) {
e.printStackTrace();
}
break;
case 7:
try {
System.out.println("Enter the position ");
int position = scanner.nextInt();
System.out.println("Insert the item ");
int data = scanner.nextInt();
list.replace(position, data);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 8:
try {
System.out.println("Note: It will give first occurence of the item ");
System.out.println("Enter the item ");
int data = scanner.nextInt();
System.out.println(list.search(data));
} catch (Exception e) {
e.printStackTrace();
}
break;
case 9:
try {
System.out.println("The Middle node of the list is :: " + list.middle());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 10:
System.out.println("Enter the position ");
try {
int position = scanner.nextInt();
System.out.println("Element is :: " + list.getElementFromLast(position));
} catch (Exception e) {
e.printStackTrace();
}
break;
case 11:
System.out.println("Reversing the list...");
System.out.println("1. Iteratively");
System.out.println("2. Recursively");
int key = scanner.nextInt();
switch (key) {
case 1:
try {
list.reverse();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 2:
try {
list.reverseRecursively();
} catch (Exception e) {
e.printStackTrace();
}
break;
default:
System.out.println("Your choice is out of the box...! ntry again...");
break;
}
break;
case 12:
try {
System.out.println("Enter first node ");
int firstNode = scanner.nextInt();
System.out.println("Enter second node ");
int secondNode = scanner.nextInt();
list.swap(firstNode, secondNode);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 13:
try {
list.swapPairwise();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 14:
try {
list.setLastNodeAsFirstNode();
} catch (Exception e) {
e.printStackTrace();
}
break;
default:
System.out.println("Your choice is out of the box...! ntry again...");
break;
}
} while (!exit);
scanner.close();
}
}