Reverse part of a linked list

Question

I'm learning data structures. I'm working on linked lists at the moment, and I'd like to have a strong grasp on them. Below is the last problem I solved. I'd like to know what you think of the solution and what can be done better.

The problem consists of reversing a linked list from position m to position n. 1 ≤ m ≤ n ≤ length of list. If we have a list 1->2->3->4->5->NULL, m = 2 and n = 4, the function should return 1->4->3->2->5->NULL.

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
 if (head == NULL || head->next == NULL || m - n == 0)
 {
 return head;
 }
 struct ListNode* prev = NULL, *cur = head;
 struct ListNode* before_m_node, *m_node, *after_n_node;
 int count = 0;
 // find m node, after loop cur points to m node, prev gets node befor or NULL if there is none
 while (count != m)
 {
 ++count;
 if (count == m)
 {
 break;
 }
 prev = cur, cur = cur->next;
 }
 m_node = cur;
 before_m_node = prev;
 prev = cur, cur = cur->next;
 // now we look for n node, cur is currently pointing to node after m, prev points to node before
 // we will reverse links as we go and after loop cur will point to n node
 while (count != n)
 {
 ++count;
 if (count == n)
 {
 break;
 }
 struct ListNode* temp = cur->next;
 cur->next = prev;
 prev = cur, cur = temp;
 }
 after_n_node = cur->next;
 // if first node is not head of the list
 if (before_m_node != NULL)
 {
 cur->next = prev;
 m_node->next = after_n_node;
 before_m_node->next = cur;
 return head;
 }
 else
 {
 cur->next = prev;
 m_node->next = after_n_node;
 return cur;
 }
}

• lifebalance: Possible duplicate?

Answer 1

Redundancy in while loops

Your while loop has a condition that never gets used because there is an if statement inside the loop that actually ends the loop. For example:

while (count != m)
{
 ++count;
 if (count == m)
 {
 break;
 }
 prev = cur, cur = cur->next;
}

You could simplify this by merging the increment into the loop condition. Also, I don't using the comma operator to put two statements on one line. So I would write your loop like this:

while (++count < m)
{
 prev = cur;
 cur = cur->next;
}

And your other loop would look like this:

while (++count < n)
{
 struct ListNode* temp = cur->next;
 cur->next = prev;
 prev = cur;
 cur = temp;
}

Use typedef

I suggest using a typedef so you don't have to use struct so much. For example:

typedef struct ListNode {
 int val;
 struct ListNode *next;
} ListNode;

And then use just ListNode instead of struct ListNode everywhere.

• Erwan Legrand: The new version of the loop does not behave as the old one in the case where the initial value of count is the same as the value of m, i.e. if the value of m is 0. I know the question assumes m to be greater than 0, but...
• JS1: @ErwanLegrand I changed the conditions to make the loops equivalent.

Answer 2

I agree with @JS1's comments. I'd add a few others.

• You could consider replacing your while loops with function calls. This could increase readability somewhat and eliminate the need for commenting at all, if you have nice function names. This would make your code more compact, though arguably slow it down since now you've got a function call. However, there are some C compile options that would support inline-ing a function.

• The more succinct a comment is, the more likely it is to be read. Even if you don't make new functions, I'd recommend shortening your comments. For example, I'd probably shorten:

  // now we look for n node, cur is currently pointing to node after m, prev points to node before // we will reverse links as we go and after loop cur will point to n node

to:

 // count to the nth code
 // reverse links during traversal

• Some of your naming could be more descriptive. For example, you could rename count to position_indicator since you are really tracking position rather than a count.

• Reduce repetitive code. In particular, you could move these two statements out of the if...else branch at the end of your function since you write the identical statement in each branch right now:

  cur->next = prev; m_node->next = after_n_node;

Answer 3

How about some defensive programming ?

• Check that m is 1 or greater
• Check that n greater or equal tom
• Check that pointers are not NULL in the loops (i.e. that you have not reached the end of the list sooner than expected)

Dereferencing a NULL pointer would lead to a segmentation fault, that is a crash.

Regarding the loops, the idiomatic C way of looping while incrementing an integer is to use for rather than while:

for (count = 1; count < m; count++) {
 if (!cur) {
 // Error handling here
 break;
 }
 prev = cur;
 cur = cur->next;
}

And assuming C99 or later, you would define count within the loop:

for (int count = 1; count < m; count++) {