在 Java 中反转连续链表的子部分

Question

我正在尝试反转单向链表的子部分，其中子部分是一组连续的偶数元素，以列表末尾或奇数元素为边界。

到目前为止，我知道如何反转链表，但我无法弄清楚如何检查元素是否奇数或是否在末尾。

Node reverse(Node head) {
// Write your code here
if(head == null) return null;
Node prev = null;
Node curr = head;
Node next = null;
while(curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

例 输入： 列表 = [1， 2， 8， 9， 12， 16]

输出： [1， 8， 2， 9， 16， 12]

此示例中的子部分是 2,8 和 12,16

Answer 1

Node reverse(Node head) {
if(head == null) return null;
Node curr = head;
Node next = null;
Node prev = null;
while(curr!=null && curr.data%2==0) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
if(curr!=head) {
head.next = curr;
curr = reverse(curr);
return prev;
} else {
head.next = reverse(head.next);
return head;
}
}

Answer 2

Q.给定一个整数的单向链表，反转每个只有偶数值的连续节点集。 I/P = 1 2 3 3 4 6 8 5，O/P= 1 2 3 3 8 6 4 5，解释- 偶数元素有两个子列表，即 [2] 和 [4->6->8]。子列表 [4->6->8] 已被反转，单个子列表 [2] 无需反转。 通过的测试用例1 3 8 3 4 2 6 5 列表中的单/多偶数元素，2 4 6 1 3甚至发生在头部，1 4 4 6 8 甚至发生到尾巴， 24 6 8 2 都在列表中

import java.util.*;
//import ds.List.ListNode; import your ListNode class
/*
public class ListNode {
public int val; 
public ListNode next;
public ListNode(int x) { val = x; next = null; }
}
*/
class Solution{
public ListNode reverseEvenElements(ListNode head)
{
ListNode p = null;//prev
ListNode c = head;//curr
while(c != null){
if(c.val % 2 == 0){
ListNode start = p;
while(c != null && c.val % 2 == 0){
p = c;
c = c.next;
}
//end of even elements = p
//making end of even node to null so that reverse should stop 
//otherwise it will reverse whole list
p.next = null;

ListNode[] node;// [head,tail]
// if start is null i.e. even element found at head itself
if(start == null){
node = reverseList(head);
head = node[0];//node[0] = head of reversed list
}else{// start != null 
node = reverseList(start.next);
start.next = node[0];
}
node[1].next = c;//node[1] = tail of reversed list
}

if(c != null){
p = c;
c = c.next;
}
}
return head;
}
// this method will be called when even elements occurs till last even element we get 
//in the original list returns head & tail of reversed list
public static ListNode[] reverseList(ListNode head){
ListNode p = null;
ListNode c = head;
ListNode n = head.next;
while(true){
c.next = p;
p = c;
c = n;
if(n == null)
break;
else 
n = n.next;
}

return new ListNode[] {p, head};// [head,tail]
}
}

Answer 3

从你给我的我理解为： 输入 ： [1,2,4,8,5,7,7,6,6,2,8,1,1,1,2,4] 输出： [1,8,4,2,5,7,7,8,2,6,6,1,1,1,4,2] 我已经编辑了您的代码以反向反转，直到这将反转间隔并创建reverse_whole，它将找到这些间隔

public ListNode reverse_whole(ListNode head) {
ListNode temp=head;
ListNode pre_temp=new ListNode(0,temp);
ListNode ans_pre = pre_temp;
while(temp!=null){
if(temp.val%2==0){
ListNode temp_till=temp;
while(temp_till!=null&& temp_till.val%2==0){
temp_till=temp_till.next;
}
// temp_till will iterate over even number interval after one 
//so: 1,2,4,6,7 : 7 is temp_till
// reverse 2,4,6 so it become : 1,6,4,2,7
pre_temp.next=reverse_subpart(temp,temp_till);
temp=temp_till;
}
pre_temp=temp;
if(temp!=null)temp=temp.next;
}
return ans_pre.next;
}
public ListNode reverse_subpart(ListNode head,ListNode end) {
// Write your code here
if(head == null) return null;
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
while(curr != end) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head.next=end;
return prev;
}

运行reverse_whole 如果你有任何疑问可以写信给我

Answer 4

class LinkedList { 
Node head; 
Node curr = head;
Node next = null;
Node prev = null;
class Node { 
int data; 
Node next; 
Node(int d) 
{ 
data = d; 
next = null; 
} 
}  

void pairWiseSwap() 
{    
Node temp = head; 
while (temp != null && temp.next!=null) { 
int k = temp.data;
int j = temp.next.data;
if(k%2==0 && j%2==0) {
temp.data=j;
temp.next.data=k;
temp=temp.next.next;
continue;
}

temp = temp.next; 
}

} 
public void push(int new_data) 
{ 
Node new_node = new Node(new_data); 
new_node.next = head; 
head = new_node; 
} 

void printList() 
{ 
Node temp = head; 
while (temp != null) { 

System.out.print(temp.data + " "); 
temp = temp.next; 
} 

System.out.println(); 
} 

public static void main(String args[]) 
{ 
LinkedList llist = new LinkedList(); 
llist.push(16); 
llist.push(12); 
llist.push(9); 
llist.push(8); 
llist.push(2); 
llist.push(1);   
System.out.println("Linked List before calling pairWiseSwap() "); 
llist.printList();   
llist.pairWiseSwap(); 
System.out.println("Linked List after calling pairWiseSwap() "); 
llist.printList(); 
} 
}