Remove Duplicates from Sorted List 체인 테이블에서 중복 값 노드 제거

6192 단어 remove
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,Given  1->1->2 , return  1->2 .Given  1->1->2->3->3 , return  1->2->3 .
제목에서 말한 바와 같이 체인표의 중복치를 증가하는 노드를 제거한다.
처음에는 다음과 같은 생각이 들었다.
  • 모든 노드를 훑어보기 위한 포인터를 설정합니다
  • 각 노드와next 노드의 값을 비교하고 같으면 현재 노드의next를next의next
  • 를 가리킨다
  • 계속 돌아다녀...
  • 그러나 문제가 있을 수 있다. {1,1,1}이면 첫 번째 1을 두루 돌아다닐 때 두 번째 1과 같다고 판단하면 첫 번째 1의next를 세 번째 1을 가리킨다.
    프로그램이 끝났습니다. 마지막으로 {1,1}로 출력하기 때문에 이 방법은 통하지 않습니다.
    위의 문제를 토대로 현재와 다음 노드의 값이 중복되는 노드를 저장하기 위해 임시 지침을 설정해야 한다. 왜냐하면 제목의 요구에 따라 체인 테이블의 값이 점차적으로 증가하기 때문이다.
    {1,1,2,3}을 예로 들면 먼저 prev 포인터를 첫 번째 1로 가리키고 (주:prev의 초기값은 노드head이며, 그next값과 같은 노드를 만났을 때 이 노드의 값을prev로 가리키며) 두 번째 1을 판단하고 교체하고, 첫 번째 1의next를 2로 가리키며, 이때prev는 첫 번째 1을 가리킨다.
    내부 순환을 설정하여 뒤에 있는 값이 prev가 가리키는 1과 같은지 판단합니다. 세 번째 1을 만났을 때 그는 1과 같기 때문에 첫 번째 1이 세 번째 1을 가리키는 넥스트를 계속 반복합니다. 값은 2입니다.
     1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode *deleteDuplicates(ListNode *head) {
    12         if(head == NULL)
    13             return head;
    14             
    15         ListNode *node = head;
    16         ListNode *prev = head;
    17         while(node->next != NULL){
    18             ListNode *cur_node = node->next;
    19             if(node->val == cur_node->val)
    20                 if(cur_node->next != NULL){
    21                     node->next = cur_node->next;
    22                     prev = node;
    23                 }else
    24                     node->next = NULL;
    25                     
    26             if(node->next != NULL)
    27                 node = node->next;
    28             
    29             while(node->val == prev->val){
    30                 if(node->next != NULL){
    31                     prev->next = node->next;
    32                     node = node->next;
    33                 }else{
    34                     prev->next = NULL;
    35                     break;
    36                 }
    37                 
    38             }
    39             
    40                     
    41         }
    42         
    43         return head;
    44         
    45     }
    46 };

    좋은 웹페이지 즐겨찾기