反向鏈接列表的右半

Question

反向第二半鏈表
例如：
偶數： 2-> 1-> 3-> 4-> 5-> 6-> 7-> 8 == ===> 2-> 1-> 3-> 4-> 8-> 7-> 6-> 5;

奇數：5-> 7-> 8-> 6-> 3-> 4 - > 2 ==> 5-> 7-> 8-> 2-> 4-> 3->如圖6所示，中間 一個也需要被反轉

class ListNode 
{ 
    int val; 
    ListNode next; 
    ListNode(int x) { val = x; } 
} 


class ReverseRightHalfLinkedList 
{ 
    public static void main(String[] args) 
    {  
     ListNode node1 = new ListNode(1); 
     ListNode node2 = new ListNode(2); 
     ListNode node3 = new ListNode(3); 
     ListNode node4 = new ListNode(4); 
     ListNode node5 = new ListNode(5); 
     node1.next = node2; 
     node2.next = node3; 
     node3.next = node4; 
     node4.next = node5; 

     ListNode res = reverse(node1);//line 31 

//  ListNode node = node1; 
//  while (node != null) 
//  { 
//   System.out.println(node.val); 
//   node = node.next; 
//  } 

    } 

    public static ListNode reverse(ListNode start) 
    { 
     int counter = 0; 
     ListNode node = start; 
     ListNode pre = start; 

     while (node!= null) 
     { 
      counter += 1; 
      node = node.next;   
     } 

     for (int i=0; i<counter/2; i++) 
     { 
      pre = start; 
      start = start.next; 
     } 

     ListNode cur = start; 

     if (counter%2 ==0) 
     { 
      while (cur != null) 
      { 
       ListNode temp = cur.next; 
       cur.next = pre; 
       pre = cur; 
       cur = temp; 
      } 
     } 
     else 
     { 
      pre = pre.next; 
      cur = start.next; 

      System.out.println(pre.val); 
      System.out.println(cur.val); 

      while (cur != null) 
      { 
       ListNode temp = cur.next; 
       cur.next = pre; 
       pre = cur; 
       cur = temp; 


       System.out.println("-----"); 
       System.out.println(pre.val); // line 90 
       System.out.println(cur.val); 
       System.out.println("-----"); 
       System.out.println(); 
      } 
     } 

     return start; 

    } 
} 

首先，我收到錯誤消息。

在 ReverseRightHalfLinkedList.main（OA2.java:31）在 ReverseRightHalfLinkedList.reverse（OA2.java:90）線程 「主」 顯示java.lang.NullPointerException異常

其次，我試圖打印反向鏈表的順序，它仍然是有序的。它沒有被扭轉。

請幫我弄清楚這兩個問題。非常感謝！

Answer 1

基礎上@激情的想法。我有一個更簡潔的代碼。

class ListNode 
{ 
    int val; 
    ListNode next; 
    ListNode(int x) { val = x; } 
} 


class ReverseRightHalfLinkedList 
{ 
    public static void main(String[] args) 
    {  
     ListNode node1 = new ListNode(2); 
     ListNode node2 = new ListNode(1); 
     ListNode node3 = new ListNode(3); 
     ListNode node4 = new ListNode(4); 
     ListNode node5 = new ListNode(5); 
     ListNode node6 = new ListNode(6); 
     ListNode node7 = new ListNode(7); 
     ListNode node8 = new ListNode(8); 
     node1.next = node2; 
     node2.next = node3; 
     node3.next = node4; 
     node4.next = node5; 
     node5.next = node6; 
     node6.next = node7; 
     node7.next = node8; 


     ListNode res = reverse(node1); 

     ListNode node = node1; 
     while (node != null) 
     { 
      System.out.println(node.val); 
      node = node.next; 
     } 

    } 

    public static ListNode reverse(ListNode start) 
    { 
     int counter = 0; 
     ListNode node = start; 
     ListNode pre = start; 

     ListNode result = start; 

     while (node!= null)// for count how many elements in linked list 
     { 
      counter += 1; 
      node = node.next;   
     } 

     for (int i=0; i< (counter/2) ; i++)//no matter counter is even or odd, when it divided by 2, the result is even 
     { 
      pre = start; 
      start = start.next; 
     } 


     ListNode temp = null; 
     ListNode preNext = null;// this variable is used to track the next val behind pre 
     // for example, 2->1->3->4->5->6->7->8 
     // at this moment, pre:4, start:5 
     // I treated 5->6->7->8 as an independent linkedlist 
     // I reversed the linkedlist 
     // Finally, set the pre node's next value to the reversed linkedlist's head 
     // The first half and second half have been connected together 


     while (start != null) 
     { 
      temp = start.next; 
      start.next = preNext; 
      preNext = start; 
      start = temp; 
     } 
     pre.next = preNext; 

     return start; 

    } 
} 

Answer 2

你需要扭轉右半列表，所以你需要保存的左半部分和列表的標題的最後一個節點，所以比在右半部分得到逆轉，您可以用左半它們鏈接，並返回整個列表。

我不得不改變你的反向方法：

public static ListNode reverse(ListNode start) 
    { 
     int counter = 0; 
     ListNode node = start; 
     ListNode pre = start; 

     ListNode result = start; 

     while (node!= null) 
     { 
      counter += 1; 
      node = node.next;   
     } 

     int end = counter % 2 == 0 ? counter/2 : (counter- 1)/2 ; 

     for (int i=0; i< end ; i++) 
     { 
      pre = start; 
      start = start.next; 
     } 


     ListNode tlist = null,temp ; 

     while(start != null){ 
      temp = start.next; 

      if(tlist == null){ 
      tlist = start; 
      start.next = null; 
      }else{ 
      start.next = tlist; 

      tlist = start; 
      } 

      start = temp; 

     } 

     pre.next = tlist; 

     return start; 

    } 

Answer 3

希望這段代碼能幫助你理解。

class MainClass { 

    public static void main(String args[]) { 

     Node head = new Node("Sameer"); 

     //Adding data to my linked list 
     Node temp = addNode("Monica", head); 
     temp = addNode("Doug", temp); 
     temp = addNode("Eric", temp); 
     temp = addNode("Charlie", temp); 
     temp = addNode("Dan", temp); 
     temp = addNode("Enrique", temp); 
     temp = addNode("Ankitha", temp); 
     addNode("Chad", temp); 

     SolveMidLinkedList(head); 
    } 

    //method to add a node to the linked list 
    static Node addNode(String str, Node node) { 
     Node newNode = new Node(str); 
     node.link = newNode; 
     return newNode; 
    } 

    //method to reverse the right hald of the linkedlist 
    static void SolveMidLinkedList(Node head) { 
     int LinkedListSize = 0; 
     Node temp = head; 
     Node LastEle = null, MiddleEle = null, temp1 = null, temp2 = null; 

     //While loop to find the size of the linkedlist and also to find the last element in the linkedlist 
     while (temp != null) { 
      LastEle = temp; 
      temp = temp.link; 
      LinkedListSize++; 
     } 

     //Printing the names 
     temp = head; 
     System.out.println("Before rearranging the linked list"); 
     while (temp != null) { 
      System.out.println(temp.name); 
      temp = temp.link; 
     } 

     //The main procedure 
     temp = head; 
     int iCount = 1; 
     while (temp != null) { 
      //Not changing the order of first half of the linked list 
      if (iCount <= (LinkedListSize/2)) { 
       MiddleEle = temp; 
      } else { 
       //Reversing the order of second half(right side half) of the linked list. 
       temp2 = temp.link; 
       temp.link = temp1; 
       temp1 = temp; 
      } 
      temp = temp.link; 
      iCount++; 
     } 
     //At the end asssigning the middle element to the last element of the linked list. 
     MiddleEle.link = LastEle; 

     //Printing the names 
     temp = head; 
     System.out.println("After rearranging the linked list"); 
     while (temp != null) { 
      System.out.println(temp.name); 
      temp = temp.link; 
     } 

    } 
} 

//General definition of Node in a linked list. 
class Node { 
    Node link = null; 
    String name; 
    Node(String str) { 
     this.name = str; 
    } 
} 

Answer 4

/* 
* To change this license header, choose License Headers in Project Properties. 
* To change this template file, choose Tools | Templates 
* and open the template in the editor. 
*/ 

package javaapplication2; 

class LinkedList { 

    static Node head; 

    static class Node { 

     int data; 
     Node next; 

     Node(int d) { 
      data = d; 
      next = null; 
     } 
    } 

    Node rev(Node node) { 
     Node prev = null; 
     Node current = node; 
     Node next = null; 
     while (current != null) { 
      next = current.next; 
      current.next = prev; 
      prev = current; 
      current = next; 
     } 
     node = prev; 
     return node; 
    } 

    Node reverse(Node node) { 
     int count =0; 
     Node doo = node; 
     Node mid_pre = node; 
     Node mid = node; 
     while(doo.next != null){ 
      if((count & 1) == 1){ 
       // mid_pre = mid; 
       mid = mid.next; 
      } 
      doo = doo.next; 
      count++; 
     } 
     // System.out.println(" midd ddddd :"+mid_pre.data+" "+mid.data); 
     mid.next = rev(mid.next); 
     return node; 
    } 

    void printList(Node node) { 
     while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
     } 

    } 

    public static void main(String[] args) { 
     LinkedList list = new LinkedList(); 
     list.head = new Node(1); 
     list.head.next = new Node(2); 
     list.head.next.next = new Node(3); 
     list.head.next.next.next = new Node(4); 
     list.head.next.next.next.next = new Node(5); 
     list.head.next.next.next.next.next = new Node(6); 

     //// 1 2 3 4 5 6 
     System.out.println("Given Linked list"); 
     list.printList(head); 
     head = list.reverse(head); 
     System.out.println(""); 
     System.out.println("Reversed linked list "); 
     list.printList(head); 
    } 
} 

Answer 5

爲什麼不能做一些非常簡單的。我們知道列表的大小。我們可以使用list.get(counter)從結尾到中心進行迭代。當名單的大小是偶數或奇數但是可行的時候有一些挑戰。

public static void reverseFromEndToCentre() { 
    List list = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10)); 

    int midOfList = (int)Math.ceil(list.size()/2); 
    int lenthOfList = list.size(); 

    int counterFirstHalf =0; 
    while(counterFirstHalf<midOfList){ 
     System.out.println(list.get(counterFirstHalf)); 
     counterFirstHalf++; 
    } 

    int counterSecondHalf = lenthOfList; 
    while(counterSecondHalf > counterFirstHalf){ 
     counterSecondHalf--; 
     System.out.println(list.get(counterSecondHalf)); 
    } 

} 

Answer 6

這是一種反轉鏈表後半部分（右）的方法。

#include<stdio.h> 
#include<stdlib.h> 

struct Node{ 
int data; 
struct Node* next; 
}; 

void append(struct Node** head_ref, int new_data) 
{ 

struct Node* new_node=(struct Node*)malloc(sizeof(struct Node)); 
new_node->data=new_data; 
new_node->next=NULL; 

struct Node* last=*head_ref; 

if(*head_ref==NULL){ 
    *head_ref=new_node; 
    return; 
} 

while(last->next!=NULL) 
    last=last->next; 

last->next=new_node; 
return; 
} 

int display(struct Node* n) 
{ 
int m=0; 
printf("\n"); 
while(n!=NULL) 
{ 
    printf(" %d ",n->data); 
    n=n->next; 
    m=m+1; 
} 
return m; 
} 

void reverse(struct Node** head_ref, int mid) 
{ 
if(*head_ref==NULL) 
{ 
    printf("\nEmpty List cannot be reversed"); 
    return; 
} 

struct Node* last=*head_ref; 
struct Node* second_last; 
struct Node* beg=*head_ref; 
int c=1; 
while(c<=mid){ 
    second_last=last; 
    last=last->next; 
    c=c+1; 
} 

struct Node* prev=NULL; 
struct Node* current=last; 
struct Node* next; 

while(current != NULL) 
{ 
    next=current->next; 
    current->next=prev; 
    prev=current; 
    current=next; 
} 
*head_ref=beg; 
second_last->next=prev; 

} 

int main() 
{ 
int size; 
struct Node* head=NULL; 
int i,mid; 
for(i=0;i<11;i++) 
{ 
    append(&head,rand()%19 +1); 
} 
size=display(head); 
printf("\n Size of linked list: %d",size); 

if(size%2==0) 
    mid=(size+1)/2; 
else 
    mid=size/2; 

reverse(&head, mid); 
display(head); 
return 0; 

}