-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDelete Pattern from Linked List of chars
98 lines (92 loc) · 2.86 KB
/
Delete Pattern from Linked List of chars
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Node{
char val;
Node next;
public Node(char c){
val = c;
next = null;
}
}
class Solution{
public static Node buildList(char[] ch){
Node n = new Node('0');
Node head = n;
for(char c :ch){
Node temp = new Node(c);
n.next = temp;
n = n.next;
}
return head.next;
}
public static void printList(Node root){
Node curr = root;
while(curr != null){
System.out.print(curr.val + "->");
curr = curr.next;
}
System.out.print("X");
System.out.println();
}
public static Node matchDelete(Node head, char[] p){
if(head == null)
return null;
//Keep a dummy node for newly generated list
Node dummy = new Node('0');
Node r = dummy;
//Put start and end as head
Node start = head;
Node end = head;
//Loop while end is not null
while(end != null){
//pattern match start
if(end.val == p[0]){
int i = 0;
while(i < p.length && end != null && end.val == p[i]){
++i;
end = end.next;
}
//If the pattern is exact match
if(i == p.length){
//Is pattern at end of list, if so mark r next as null and return
if(end == null){
r.next = null;
return dummy.next;
}else{
//skip all elements till end
start = end;
}
}else{
//pattern matched partially, always put first start in list and skip still start matches end or matches p[0]
while( start != null && start != end) {
r.next = start;
start = start.next;
r = r.next;
if(start != null && start.val == p[0]){
end = start;
break;
}
}
}
}else{
//no match copy to r list
r.next = start;
start = start.next;
end = end.next;
r = r.next;
}
}
r.next = null;
return dummy.next;
}
}
public class MatchAndDelete {
public static void main(String args[]) {
char[] list = "111111111".toCharArray();
char[] pattern = "111111111".toCharArray();
System.out.println("List:-");
Node head = Solution.buildList(list);
Solution.printList(head);
System.out.println("Result:");
Node result = Solution.matchDelete(head,pattern);
Solution.printList(result);
}
}