Skip to content

Commit 77bcd4d

Browse files
funCodeSonalifunCodeSonali
authored
Fix singly linked list (TheAlgorithms#2988)
1 parent 63f486c commit 77bcd4d

2 files changed

Lines changed: 139 additions & 143 deletions

File tree

‎pom.xml‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,14 @@
4343
<artifactId>maven-surefire-plugin</artifactId>
4444
<version>2.22.2</version>
4545
</plugin>
46+
<plugin>
47+
<groupId>org.apache.maven.plugins</groupId>
48+
<artifactId>maven-compiler-plugin</artifactId>
49+
<configuration>
50+
<source>16</source>
51+
<target>16</target>
52+
</configuration>
53+
</plugin>
4654
</plugins>
4755
</build>
4856
</project>

‎src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java‎

Lines changed: 131 additions & 143 deletions
Original file line numberDiff line numberDiff line change
@@ -44,16 +44,14 @@ public SinglyLinkedList(Node head, int size) {
4444
public boolean detectLoop() {
4545
Node currentNodeFast = head;
4646
Node currentNodeSlow = head;
47-
boolean flag = false;
48-
while (currentNodeFast != null && currentNodeFast.next != null && currentNodeSlow != null && currentNodeSlow.next != null) {
47+
while (currentNodeFast != null && currentNodeFast.next != null) {
4948
currentNodeFast = currentNodeFast.next.next;
5049
currentNodeSlow = currentNodeSlow.next;
5150
if (currentNodeFast == currentNodeSlow) {
52-
flag = true;
53-
break;
51+
return true;
5452
}
5553
}
56-
return flag;
54+
return false;
5755
}
5856

5957
/**
@@ -84,7 +82,7 @@ public void swapNodes(int valueFirst, int valueSecond) {
8482
if(previousA != null){
8583
previousA.next = currentB;
8684
}
87-
else{
85+
else{
8886
// make 'b' as the new head
8987
head = currentB;
9088
}
@@ -98,7 +96,7 @@ public void swapNodes(int valueFirst, int valueSecond) {
9896
head = currentA;
9997
}
10098
// Swap next pointer
101-
99+
102100
Node temp = currentA.next;
103101
currentA.next = currentB.next;
104102
currentB.next = temp;
@@ -109,15 +107,19 @@ public void swapNodes(int valueFirst, int valueSecond) {
109107
*
110108
*/
111109
Node reverseList(Node node) {
110+
Node prevNode = head;
111+
while(prevNode.next!=node){
112+
prevNode = prevNode.next;
113+
}
112114
Node prev = null, curr = node, next;
113115
while (curr != null) {
114116
next = curr.next;
115117
curr.next = prev;
116118
prev = curr;
117119
curr = next;
118120
}
119-
node = prev;
120-
return node;
121+
prevNode.next = prev;
122+
return head;
121123
}
122124

123125
/**
@@ -161,6 +163,14 @@ public Node getHead() {
161163
return head;
162164
}
163165

166+
/**
167+
* Set head of the list.
168+
*
169+
*/
170+
public void setHead(Node head) {
171+
this.head = head;
172+
}
173+
164174
/**
165175
* Calculate the count of the list manually
166176
*
@@ -205,145 +215,41 @@ public String toString() {
205215
return joiner.toString();
206216
}
207217

208-
/**
209-
* Driver Code
210-
*/
211-
public static void main(String[] arg) {
212-
SinglyLinkedList list = new SinglyLinkedList();
213-
assert list.isEmpty();
214-
assert list.size() == 0 && list.count() == 0;
215-
assert list.toString().equals("");
216-
217-
/* Test insert function */
218-
list.insertHead(5);
219-
list.insertHead(7);
220-
list.insertHead(10);
221-
list.insert(3);
222-
list.insertNth(1, 4);
223-
assert list.toString().equals("10->7->5->3->1");
224-
225-
/* Test search function */
226-
assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);
227-
228-
/* Test get function */
229-
assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;
230-
231-
/* Test delete function */
232-
list.deleteHead();
233-
list.deleteNth(1);
234-
list.delete();
235-
assert list.toString().equals("7->3");
236-
237-
assert list.size == 2 && list.size() == list.count();
238-
239-
list.clear();
240-
assert list.isEmpty();
241-
242-
try {
243-
list.delete();
244-
assert false;
245-
/* this should not happen */
246-
} catch (Exception e) {
247-
assert true;
248-
/* this should happen */
249-
}
250-
251-
Node instance = new Node();
252-
Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
253-
head = instance.deleteDuplicates(head);
254-
instance.print(head);
255-
256-
}
257-
}
258-
259-
/**
260-
* This class is the nodes of the SinglyLinked List. They consist of a value and
261-
* a pointer to the node after them.
262-
*/
263-
class Node {
264-
265-
/**
266-
* Head refer to the front of the list
267-
*/
268-
public Node head;
269-
270-
/**
271-
* Size of SinglyLinkedList
272-
*/
273-
public int size;
274-
275-
276-
277-
/**
278-
* The value of the node
279-
*/
280-
int value;
281-
282-
/**
283-
* Point to the next node
284-
*/
285-
Node next;
286-
287-
Node() {
288-
}
289-
290-
/**
291-
* Constructor
292-
*
293-
* @param value Value to be put in the node
294-
*/
295-
Node(int value) {
296-
this(value, null);
297-
}
218+
public void deleteDuplicates() {
298219

299-
/**
300-
* Constructor
301-
*
302-
* @param value Value to be put in the node
303-
* @param next Reference to the next node
304-
*/
305-
Node(int value, Node next) {
306-
this.value = value;
307-
this.next = next;
308-
}
309-
310-
public Node deleteDuplicates(Node head) {
311-
// sentinel
312-
Node sentinel = new Node(0, head);
313-
314-
// predecessor = the last node
315-
// before the sublist of duplicates
316-
Node pred = sentinel;
317-
318-
while (head != null) {
220+
Node pred = head;
221+
// predecessor = the node
222+
// having sublist of its duplicates
223+
Node newHead = head;
224+
while (newHead != null) {
319225
// if it's a beginning of duplicates sublist
320226
// skip all duplicates
321-
if (head.next != null && head.value == head.next.value) {
227+
if (newHead.next != null && newHead.value == newHead.next.value) {
322228
// move till the end of duplicates sublist
323-
while (head.next != null && head.value == head.next.value) {
324-
head = head.next;
229+
while (newHead.next != null && newHead.value == newHead.next.value) {
230+
newHead = newHead.next;
325231
}
326232
// skip all duplicates
327-
pred.next = head.next;
233+
pred.next = newHead.next;
234+
newHead = null;
235+
328236
// otherwise, move predecessor
329-
} else {
330-
pred = pred.next;
331237
}
332-
333238
// move forward
334-
head = head.next;
239+
pred = pred.next;
240+
newHead = pred;
335241
}
336-
return sentinel.next;
337242
}
338243

339-
public void print(Node head) {
244+
public void print() {
340245
Node temp = head;
341246
while (temp != null && temp.next != null) {
342247
System.out.print(temp.value + "->");
343248
temp = temp.next;
344249
}
345250
if (temp != null) {
346251
System.out.print(temp.value);
252+
System.out.println();
347253
}
348254
}
349255

@@ -379,39 +285,29 @@ public void insertNth(int data, int position) {
379285
head = newNode;
380286
size++;
381287
return;
382-
} else if (position == 0) {
288+
}
289+
if (position == 0) {
383290
/* insert at the head of the list */
384291
newNode.next = head;
385292
head = newNode;
386293
size++;
387294
return;
388295
}
296+
389297
Node cur = head;
390298
for (int i = 0; i < position - 1; ++i) {
391299
cur = cur.next;
392300
}
393301
newNode.next = cur.next;
394302
cur.next = newNode;
395303
size++;
304+
396305
}
397306

398307
/**
399308
* Swaps nodes of two given values a and b.
400309
*
401310
*/
402-
public void swapNodes(int a, int b) {
403-
Node currentNode = head;
404-
Node temp = null;
405-
while (currentNode != null) {
406-
if (currentNode.next.value == a) {
407-
temp = currentNode.next;
408-
}
409-
if (currentNode.next.value == b) {
410-
currentNode.next = temp;
411-
}
412-
currentNode = currentNode.next;
413-
}
414-
}
415311

416312
/**
417313
* Deletes a node at the head
@@ -479,4 +375,96 @@ public void checkBounds(int position, int low, int high) {
479375
throw new IndexOutOfBoundsException(position + "");
480376
}
481377
}
378+
/**
379+
* Driver Code
380+
*/
381+
public static void main(String[] arg) {
382+
SinglyLinkedList list = new SinglyLinkedList();
383+
assert list.isEmpty();
384+
assert list.size() == 0 && list.count() == 0;
385+
assert list.toString().equals("");
386+
387+
/* Test insert function */
388+
list.insertHead(5);
389+
list.insertHead(7);
390+
list.insertHead(10);
391+
list.insert(3);
392+
list.insertNth(1, 4);
393+
assert list.toString().equals("10->7->5->3->1");
394+
System.out.println(list.toString());
395+
/* Test search function */
396+
assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);
397+
398+
/* Test get function */
399+
assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;
400+
401+
/* Test delete function */
402+
list.deleteHead();
403+
list.deleteNth(1);
404+
list.delete();
405+
assert list.toString().equals("7->3");
406+
System.out.println(list.toString());
407+
assert list.size == 2 && list.size() == list.count();
408+
409+
list.clear();
410+
assert list.isEmpty();
411+
412+
try {
413+
list.delete();
414+
assert false;
415+
/* this should not happen */
416+
} catch (Exception e) {
417+
assert true;
418+
/* this should happen */
419+
}
420+
421+
SinglyLinkedList instance = new SinglyLinkedList();
422+
Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
423+
instance.setHead(head);
424+
instance.deleteDuplicates();
425+
instance.print();
426+
427+
}
428+
429+
}
430+
431+
/**
432+
* This class is the nodes of the SinglyLinked List. They consist of a value and
433+
* a pointer to the node after them.
434+
*/
435+
class Node {
436+
437+
/**
438+
* The value of the node
439+
*/
440+
int value;
441+
442+
/**
443+
* Point to the next node
444+
*/
445+
Node next;
446+
447+
Node() {
448+
}
449+
450+
/**
451+
* Constructor
452+
*
453+
* @param value Value to be put in the node
454+
*/
455+
Node(int value) {
456+
this(value, null);
457+
}
458+
459+
/**
460+
* Constructor
461+
*
462+
* @param value Value to be put in the node
463+
* @param next Reference to the next node
464+
*/
465+
Node(int value, Node next) {
466+
this.value = value;
467+
this.next = next;
468+
}
469+
482470
}

0 commit comments

Comments
 (0)