如何遍歷前面兩個節點的鏈接列表？

我有一個鏈接列表，我希望能夠看到前面的兩個節點。我需要檢查前兩個節點是否有整數，如果有，並且第三個節點說ADD，那麼我需要將這些信息壓縮到一個節點並釋放其他兩個節點。如何遍歷前面兩個節點的鏈接列表？

我很困惑我的while循環中應該發生什麼。我檢查第三個節點是否指向null，但不知何故，這並沒有給我正確的輸出。我不知道我是否正確處理我的node.next。其中一些現在是僞代碼。

while(node1.next.next.next != NULL){ 
    if((node1.data.isInteger() && (node2.data.isInteger()){ 
     if(node3.data.equals('add')){ 
      node1.data = node1.data + node2.data; 
     } else { 
      //ERROR 
     } 
     garbage_ptr1 = node2; 
     garbage_ptr2 = node3; 
     node1.next = node3.next; 
     free(garbage_ptr1); 
     free(garbage_ptr2); 
     node2.next = node1.next.next; 
     node3.next = node2.next.next; 
    } else { 
     node1.next = node1.next.next; 
     node2.next = node1.next.next; 
     node3.next = node2.next.next; 
    }

來源

2013-02-27 Jay

嘗試迭代（移動）你以相反的順序列出：當你看到運營商加入你知道你必須要總結兩個操作數，這兩個未來。 – Aubin 2013-02-27 19:41:50

你的while循環內部不能循環節點來展望未來2？ – SMT 2013-02-27 19:42:40

它是'隊列'還是'deque'？ – bsiamionau 2013-02-27 19:43:41

我覺得比較容易的方法是維護一個小數組，作爲列表上的一個窗口並查找數組上的匹配。如果將空檢查移到實用程序方法中，代碼也會變得更清晰和更簡單。通過做這些事情，循環遍歷列表只需要檢查窗口的最後一個元素來終止。

的這個Java中的草圖：

/* small utility methods to avoid null checks everywhere */ 
public static Node getNext(Node n) { return n != null ? n.next : null; } 

public static boolean isInteger(Node n) { 
    return (n != null) && (n.data != null) && (n.data instanceof Integer); 
} 
public static boolean isAdd(Node n) { 
    return (n != null) && (n.data != null) && n.data.equals("add"); 
} 

/* checks for a match in the 3-node window */ 
public boolean isMatch(Node[] w) { 
    return isInteger(w[0]) && isInteger(w[1]) && isAdd(w[2]); 
} 

/* Loads the 3-node window with 'n' and the next two nodes on the list */ 
public void loadWindow(Node[] w, Node n) { 
    w[0] = n; w[1] = getNext(w[0]); w[2] = getNext(w[1]); 
} 

/* shifts the window down by one node */ 
public void shiftWindow(Node[] w) { loadWindow(w, w[1]); } 

... 
Node[] window = new Node[3]; 
loadWindow(window, node1); 
while (window[2] != null) { 
    if (isMatch(window)) { 
    window[0].data = stack[0].data + stack[1].data; 
    window[0].next = window[2].next; 
    loadWindow(window, window[0]); // reload the stack after eliminating two nodes 
    } else { 
    shiftWindow(window); 
    } 
}

來源

2013-03-08 16:53:51 sfstewman

如何遍歷前面兩個節點的鏈接列表？

回答

相關問題