奇偶链表
我们有一个整数链表,编写一个函数来修改链表,使得修改后的链表中所有偶数出现在所有奇数之前。另外,保持偶数的顺序相同。
我在互联网上看到了给定问题的解决方案,但无法理解代码中的第 62 行。这是做什么用的?
我花了一整天的时间,但无法想出其中的逻辑。如果有人帮助我那就太好了。
public class OddEven {
public class Node{
int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}
public static Node head;
public static Node tail;
public void addFirst(int data){
Node newNode = new Node(data);
if(head == null){
head = tail = newNode;
return;
}
newNode.next = head;
head = newNode;
}
public void print(){
Node temp = head;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public void segregateEvenOdd(){
Node end = tail;
Node prev = null;
Node curr = head;
Node new_end = end;
while(curr.data%2 != 0 && curr != end){
new_end.next = curr;
curr = curr.next;
new_end.next.next = null;
new_end = new_end.next;
}
if(curr.data%2 == 0){
head = curr;
while(curr != end){
if(curr.data % 2 == 0){
prev = curr;
curr = curr.next;
}
else{
prev.next = curr.next;
curr.next = null;
new_end.next = curr;
new_end = curr;
curr = prev.next;
}
}
}
else prev = curr;
if(new_end != end && end.data %2 != 0){
prev.next = end.next;
end.next = null;
new_end.next = end;
}
}
public static void main(String args[]){
OddEven ll = new OddEven();
ll.addFirst(9);
ll.addFirst(1);
ll.addFirst(4);
ll.addFirst(5);
ll.addFirst(10);
ll.addFirst(12);
ll.addFirst(8);
System.out.println("Linked list before :");
ll.print();
ll.segregateEvenOdd();
System.out.println("Updated linked list :");
ll.print();
}
}
不知道你的第 62 行在哪里,但我认为是这两行:
else prev = curr;
或 if(new_end != end && end.data %2 != 0)
第62行:
else prev = curr;
当当前节点是奇数并且您不交换它时,
else prev = curr;
行会更新prev
节点。该行用作您评估的最近节点的记录,以便您可以在后续迭代中正确处理指针。
第62行:
if(new_end != end && end.data %2 != 0)
用于解决或处理原始链表的最后一个节点是奇数的情况。基本上它将用于确保列表中原始的最后一个节点是奇数并且尚未位于新列表的末尾。
new_end != end: // used to check new end node on the list
end.data % 2 != 0: // used to check original last node 'end' if it is odd
如果两个条件都为真,您的
if
块将被执行。