Print pairs of values that are in a linked list

Question

This is my code for creating a linked list:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct list_element {
    int inf;
    struct list_element *next;
} List;

List *create() {
    List *p, *punt;
    int x = 1;/*Random number but different from 0*/
    p = (List *)malloc(sizeof(List));
    printf("\nFirst value: ");
    scanf("%d", &p->inf);
    punt = p;

    while (1) {/*Till x different from 0*/
        printf("\nNext value: ");
        scanf("%d", &x);
        if (x == 0)
            break;
        punt->next = (List *)malloc(sizeof(List));
        punt = punt->next;
        punt->inf = x;
    }
    punt->next = NULL;
    return p;
}

int main(void) {
    List *a;
    a = create();
}

Suppose the following values to be sent in input(scanf):

10 20 30 40 50 15 35

I need to create a void function which sends to stdout the list of pairs of numbers whose sum is 50, so in this case the output will be

10 40

20 30

15 35

To do this I used two different functions:
In the first I copied the the value of the linked list in an array of int and in the second function, with a backtracking algorithm (performed on the array just created) I found the solutions.
This is my solution:

void BackTrack(int n, int s, int x[7], int z[7], int partial, int max, int check) {
    if (n == s) {
        int y = 0;
        for (int i = 0; i < n; i++){
            if (z[i] != 0 && check == 2 && partial == max) {
                printf("%d ", z[i]);
                y++;
            }
        }
        if(y != 0)
            printf("\n");
        return;
    }

    z[s] = 0;
    BackTrack(n, s + 1, x, z, partial, max, check);

    if (x[s] + partial <= max) {
        z[s] = x[s];
        partial += x[s];
        check++;
        BackTrack(n, s + 1, x, z, partial, max, check);
    }
}

void ARRAY(List *p) {
    int *x = NULL;
    int i;
    for (i = 0; p != NULL; i++){
        x = realloc(x, sizeof(int) * (i + 1));
        x[i] = p->inf;
        p = p->next;
    }
    int *z = malloc(sizeof(int) * i);
    BackTrack(i, 0, x, z, 0, 50, 0);
}

But I wanna know if there is a way to do this without using before an array conversation as I did? So to fint directly the couples on the linked list. Thanks

Possible duplicate of [Design an algorithm to find all pairs of integers within an array which sum to a specified value](http://stackoverflow.com/questions/1494130/design-an-algorithm-to-find-all-pairs-of-integers-within-an-array-which-sum-to-a) — Saeid, Sep 30 '16 at 10:59
@Tempux not really, i do not want to find pairs in the array (because I already proposed here above my solution with that method), i wanted to know if there is a way to do the same thing but on a linked list — Amarildo, Sep 30 '16 at 11:02
`p = (List *)malloc(sizeof(List));` <-- please don't cast the return of `malloc` & co. It's required in C++, but considered harmful in C — Elias Van Ootegem, Sep 30 '16 at 11:10

score 2 · Accepted Answer · answered Sep 30 '16 at 11:49

2

void FindPairs(List *list, int sum) {

  struct list_element *i, *j;

  for (i = list; i; i = i->next) {
    if (i->inf > sum)
      continue;
    for (j = i->next; j; j = j->next) {
      if (i->inf + j->inf == sum)
        printf("%d %d\n", i->inf, j->inf);
    }
  }
}

answered Sep 30 '16 at 11:49

G. Sliepen

7,637
1
15
31

OMG, I never thought to use a for loop in this way. Nice – Amarildo Sep 30 '16 at 11:56

score 0 · Answer 2 · answered Jan 06 '17 at 06:57

Simple method would be using 2 for loops over the list and check for required sum, Complexity - O(n^2).
Use hashmap, store first value in hash map, now from 2nd value, if sum-2ndValue exist in hashmap, your solution, else insert in hashmap. - Time Complexity - O(n), Space Complexity - O(n).

MrSmith42 · Answer 3 · 2016-10-27T10:21:55.193

I you have the space, copy all values in a sorted data structure like a sorted list. Than you can simultan iterate from both sides and find the pairs this way.

Speed:

create the sorted list: O(n log n)
iterate to find the pairs: O(n)

if you have not enough space, you need to iterate through the linked list very often.

Pseudocode:

nodeLeft=fistNodeInList
while(nodeLeft.hasNext)
  nodeRight=nodeLeft
  while(nodeRight.hasNext)
    nodeRight= nodeRight.next
    if(nodeRight.value+nodeLeft.value= sum
      print odeRight.value nodeLeft.value
  nodeLeft=nodeLeft.next

This has O(n²) speed

Print pairs of values that are in a linked list

3 Answers3