InterviewBitのLinkedList関数

Question

私の解決策に苦労していますfor a question on InterviewBit。

私は完全な説明にリンクされているが、短期的に：

1）あなたはLinkedListの

2のヘッドノードを与えられている）、リストの最初の半分を取るとなるように値を変更します。

「第一ノードの新しい値=最後のノードの値 - 最初のノードの現在の値 第二ノードの新しい値=最後から二番目のノードの値 - 第二のノードの現在の値」

これは私のアプローチです（それはコンパイルされますが、リストをまったく変更しません）

私の方法では実際に元のリストが変更されていないことがわかります - 私は新しいリストを作成しているようです正しく変更された値は元の値に変更されません。

/** 
* Definition for singly-linked list. 
* class ListNode { 
*  public int val; 
*  public ListNode next; 
*  ListNode(int x) { val = x; next = null; } 
* } 
*/ 
public class Solution { 
    public ListNode subtract(ListNode a) { 
     ListNode current = a; 
     int length = 0; 

     //get length 
     while(current.next != null){ 
      length++; 
      current = current.next; 
     } 

     length += 1; 

     while(current.next != null){ 

      double half = Math.floor(length/2); 

      for(int i=0; i<half; i++){ 
       // 
       // if(i == 0){ 
       //  int aval = (nthToLast(a, length)).val - a.val; 
       //  a.val = ((nthToLast(a, length-i)).val - a.val); 
       //  a.next = current; 
       // } 
       current.val = ((nthToLast(a, length-i)).val - current.val); 
       current = current.next; 
      } 

     } 
     return a; 

    } 

    /* Helper function that given LinkedList head, and int n, 
returns the nth to last ListNode in the LinkedList */ 

    public ListNode nthToLast(ListNode head, int n){ 
     ListNode nth = head; 
     ListNode ahead = head; 

     /* strategy: set nth to head, and 'ahead' to n places in front of 'nth' 
      increment at same speed and then when 'ahead' reaches the end, 'nth' 
      will be in the nth place from the end. 
     */ 

     while(ahead.next != null){ 
      for(int i=0; i<n; i++){ 
       ahead = ahead.next; 
      } 

      nth = nth.next; 
      ahead = ahead.next; 
     } 

     return nth; 
    } 
} 

また、私はこれらのような質問でより良くなるよう努力しています。これはこの質問のための良いアプローチですか？私はこの作業を行う方法を理解したいと思いますが、これが悪いアプローチの場合は私に教えてください。シンプルなヘルパー関数に

Answer 1

ブレークコードは、 は、関数（この関数は書くことは非常に容易である） リンクリストのn番目の要素の値を取得した後、半分件までにその関数を呼び出すたびに、リストを横断する作りますリストのlistSize-iメンバの値を取得し、リストのi番目のメンバの値を編集します。あなたのリンクリストの実装が動作しているかどうかを確認するために、最初のいくつかの要素を手動で変更してください。

/** 
* Definition for singly-linked list. 
**/ 
class ListNode { 
    public int val; 
    public ListNode next; 
    ListNode(int x) { val = x; next = null; } 
} 

public class Solution { 
    public ListNode subtract(ListNode a) { 
     ListNode current = a; 
     int length = 0; 
     //get length 
     while(current.next != null){ 
      length++; 
      current = current.next; 
     } 
     length += 1; 
     int half = length/2; 
     //logic of this loop is 
     //go from 0 to half of the list 
     // j goes from the last element to half 
     //for example if size of list is 6 (indexing from 0) 
     //when i is 0 j is 5 
     //when i is 1 j is 4 and so on 
     //so you get what you wanted 
     for(int i=0,j=length-1; i<half; i++,j--){ 
      current.val=nthElement(a,j).val-current.val; 
      current = current.next; 
     } 
     return a; 
    } 
    /* Helper function that given LinkedList head, and int n, 
    returns the nth node of LinkedList */ 
    public ListNode nthElement(ListNode head, int n){ //e.g-if n is 5 it will return the 5th node 
     ListNode nth = head; 
     for(int i=0; i<n; i++){ 
      nth = nth.next; 
     } 
     return nth; 
    } 
}